5. 平衡搜索树

习题

#30017

⚡5⏳5

实现只支持插入的 AVL 整数树：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct AvlTree AvlTree;

AvlTree *avl_create(void);
void avl_destroy(AvlTree *tree);
bool avl_insert(
    AvlTree *tree,
    int64_t key,
    bool *out_inserted
);
bool avl_contains(const AvlTree *tree, int64_t key);
bool avl_validate(const AvlTree *tree);

要求：

1. 重复键插入成功返回并设置 *out_inserted = false；新结点由树拥有。
2. 每个结点保存高度或等价信息；插入后每个结点的平衡因子必须位于 [-1, 1]。
3. 正确处理 LL、RR、LR、RL 四种旋转；分配失败或大小计算溢出时树保持不变。
4. avl_validate 必须检查搜索树顺序、结点高度和所有平衡因子，不能只检查根结点。
5. 查找和插入时间复杂度为 $O(\log n)$，验证时间复杂度为 $O(n)$；destroy(NULL) 安全。