1.简介

二叉排序树可以加快我们查询某个元素的速度，但是极端情况下二叉排序树的不平衡会大大影响查询效率。因此，就有一些牛人去研究如何让二叉排序树尽可能的平衡。于是就出现了平衡二叉（排序）树的概念。目前我所知道的平衡二叉树有2种，AVL树和红黑树。

  1.   - AVL树：AVL是这个树发明者的名字首字母，AVL树保证二叉树平衡的规则是保持左右子树的高度差在1的范围内（左子树的高度 和 右子树的高度之差的绝对值 <= |1|）
  2.   - 红黑树（Red-And-Black Tree）: 这个名字的由来是因为这种平衡二叉树的节点非黑即红的特性。其保证二叉树平衡的规则在下一节中讲述
  3.   - 区别：都是平衡二叉树，AVL树更平衡一点，红黑树应用更广泛

2.性质

  1. 所有节点非黑即红

image.png

  1. 根节点必须为黑色

image.png

  1. 红色节点的左右孩子不可再为红色

image.png

  1. 每个节点到叶子节点的路径上的黑色节点的个数一致

image.png

  1. 所有的子节点都是 黑色的且是 null （其实这条无所谓）

image.png

  1. 新增节点都是红色

image.png

3.小结

满足了上面规则的树就是平衡的二叉树，我们在新增或删除节点后要保证整颗树仍然遵守上面的规则（性质），新增节点或删除节点前后树可能就不满足这些性质，于是需要进行不同调整。下一节我们就开始聊一聊红黑树的插入过程。