【数据结构】树-平衡二叉树

王道课程地址

简称平衡树（AVL 树），指树上任一结点的左子树和右子树的高度之差（平衡因子）不超过 1。

摘要

1. 插入操作导致不平衡时只需要调整最小不平衡子树就可以让树恢复平衡。
2. 含有 n 个结点的平衡二叉树的最大深度为 O(log2n)，平均查找长度为O(log2n)。
3. 用n{h}表示高度为 h 的平衡二叉树最少结点数，则 n{h} = n{h-1} + n{h-2} + 1，其中 n{0} == 0，n{1} == 1，n{2} = 2。

概念

结点的平衡因子

结点的左子树高度-右子树高度

调整最小不平衡子树

插入导致树不平衡的所有可能如下：

• LL：在树的左孩子的左子树中插入导致不平衡。 树的左子树右旋，保持平衡及排序。
• RR：在树的右孩子的右子树中插入导致不平衡。 树的右子树左旋，保持平衡及排序。
• LR：在树的左孩子的右子树中插入导致不平衡。 树的左孩子的右孩子先左旋再右旋。
• RL：在树的右孩子的左子树中插入导致不平衡。 树的右孩子的左子树先右旋再左旋。