平衡二叉树重新学习。

二叉排序树可能退化成一个链表的缺点，可以使用平衡二叉树来解决。平衡二叉树具有二叉排序树所有特点，新增了一个特性来保证树的平衡：每个结点的左子树和右子树的高度差的绝对值不超过1。

平衡二叉树基于这样的特点，可以保证不会出现大量的结点偏向于一边的情况。

平衡二叉树的插入操作

平衡二叉树插入一个结点后可能导致平衡被破坏，需要调整该不平衡子树，达到新的平衡。

插入新结点有多种情况需要调整平衡：

• LL型，在一个结点的左子结点（L）的左子结点（L）进行插入，需要进行向右旋转。
• RR型，在一个结点的右子结点（R）的右子结点（R）进行插入，需要进行向左旋转。
• LR型，在一个结点的左子结点（L）的右子结点（R）进行插入，需要先进行一次向左旋转，再进行一次向右旋转。
• RL型，在一个结点的右子结点（R）的左子结点（L）进行插入，需要先进行一次向右旋转，再进行一次向左旋转。

LL型调整

当在B的左（L）孩子A的左（L）子树上插入结点时，需要向右旋转，B的左孩子A作为新的根节点，将A原来的右子树变为B的左子树，B变为A的右子树。

RR型调整

当在A的右（R）孩子的右（R）子树上插入结点时，需要向左选准，A的有孩子B作为新的根节点，B的左子树变为A的右子树，A变为B的左子树。

LR型调整

当在C的左（L）孩子A的右（R）子树B上插入结点时，需要先将A向左旋转，变成LL型，再将C向右旋转，B作为新的根节点，A作为B的左孩子，C作为B的右孩子。

RL型调整

当在A的右（R）孩子C的左（L）子树B上插入结点时，需要先将C向右旋转，变成RR型，再将A向左旋转，B作为新的根节点，A作为B的左孩子，C作为B的右孩子。

平衡二叉树分析

时间复杂度

• 复杂度为$O(nlog_2n)$

缺点

平衡二叉树在每次插入和删除结点的时候，几乎都会破坏平衡，需要进行旋转调整平衡，在插入和删除频繁的场景中，频繁的平衡调整会影响性能。

红黑树可以解决平衡二叉树的缺点，红黑树在插入和查找过程中不会频繁破坏红黑树的平衡，不需要频繁调整。

参考内容

• 《数据结构（Java版）》