01.树


02.二叉树和二叉平衡树

03.平衡二叉树的恢复

将导致不平衡的结点称作被破坏者，破坏了结点的平衡的结点成为破坏者，经过调整可以让该树平衡的结点称为调整结点。

LL型：
以被破坏者的左孩子结点作为调整结点，对其进行右旋。如果调整结点有右子树，将其右子树作为被破坏者的左子树。

LR型：
以被破坏者的左孩子的右孩子结点为调整结点。
如果破坏者为调整结点的左孩子，以调整结点进行左旋，将破坏者作为调整结点的父节点的右子树，后进行右旋，破坏者位置保持不变。
如果破坏者为调整结点的右孩子，以调整结点进行左旋，破坏者位置保持不变。后进行右旋，将破坏者作为被破坏者的左子树。

RR型：
以被破坏者的右孩子结点为调整结点，对其进行左旋。如果调整结点有左子树，将其右子树作为被破坏者的右子树。

RL型：
以被破坏者的右孩子的左孩子结点为调整结点。
如果破坏者为调整结点的左孩子，以调整结点进行右旋，破坏者位置保持不变，后进行左旋，将破坏者作为被破坏者的右子树。
如果破坏者为调整结点的右孩子，以调整结点进行右旋，将破坏者作为调整结点的父节点的左子树。后进行左旋，破坏者位置保持不变。

---

红黑树：

红黑树是一种自平衡的二叉查找树，是一种高效的查找树。