平衡二叉搜索树

定义：在二叉搜索树的基础上，任意一个节点的左右子树的高度相差不能大于 1。（又叫AVL树）
image.png

平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不会出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相 应的插入、删除、查找等操作的效率高一些

失衡后会进行自旋平衡：
image.png
特点：自旋前后中序遍历是一样的

红黑树

“Red-Black Tree”，简称 R-B Tree。追求近似平衡
红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：

  1. 根节点是黑色的；
  2. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  3. 任何相邻的节点都不能同时为红色
  4. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点