-
红黑树的几个特点
- 首先他是一颗BST树
- 叶子节点只有红色或黑色
- 根是黑色
- 所有叶子节点都是黑色
- 每个红色节点必须有两个黑色的子节点
- 从任一节点到每个叶子结点的所有简单路径都包含相同数目的黑色节点(所以任意一个根节点左右子树高度最高相差二倍,解释:极端情况如果左侧全为黑色,右侧红黑交替,在保证路径包含相同数目的黑色节点的情况下,右边最多为左边二倍,这也是他作为平衡树的一个基准)
-
插入过程
- 如果当前节点作为根节点,把根节点变为黑色
- 如果节点父节点是黑色节点,不变
- 每次插入都是作为红色插入,
- 如果插入位置的叔叔节点为红色,那么父亲和叔叔变为黑色,祖父节点变为红色,再向上检查
- 如果插入位置的叔叔节点不存在或者为黑色,进行旋转操作,然后调整变色,父节点变黑,祖父节点被旋转下来了,变为红色,再向上检查
不深入了解,只谈谈特点和插入过程,删除过程较为复杂,问的较少,以后找机会补上
