【数据结构】红黑树(Red-Black Tree)

前言在上一篇博客中我们学习了 AVL 树为了保持绝对的平衡它在插入和删除时会疯狂地进行左旋和右旋。但在现代的Java集合框架中如TreeMap、TreeSet以及 Java 8 之后的HashMap并没有选择 AVL 树而是选择了红黑树Red-Black Tree。一、为什么有了 AVL 树还要红黑树AVL树的特点任何节点的左右子树高度差绝对不能超过 1。这导致了一个致命问题查询确实快了但每次插入或删除数据时为了维持这种极度的平衡树结构需要极其频繁地进行旋转调整。红黑树的诞生就是为了解决这个痛点。 它是一种“弱平衡”的二叉查找树。它不再追求左右两边高度的绝对一致它的平衡规则是通过“红黑规则”进行实现的。红黑树特点是一个二叉查找树。但是不是高度平衡的。特有的红黑规则。二、红黑树五大规则节点非黑即红每一个节点或是红色或者是黑色的。根节点必黑根节点必须是黑色的。叶子节点必黑如果一个节点没有子节点或者父节点则改节点相应的指针属性值为Nil这些Nil视为叶节点每个叶节点Nil是黑色的。红必连黑如果一个节点是红色的那么它的两个子节点必须都是黑色的。黑高一致最重要的一条从任意一个节点出发走到其所有后代叶子节点NIL的简单路径上包含的黑色节点数量必须完全相同。三、红黑树添加节点的规则1.引例默认颜色添加节点默认是红色的效率最高。若默认颜色是黑色会发生什么此时违背了五大规则的最后一条从任意节点出发走到其后代的叶节点的所有简单路径上黑色节点数量一样。要把添加的18节点变成红色。此时又有一个节点添加进来此时仍旧违背了第五条规则。由上述例子可知如果默认节点为黑色添加三个节点要调整两次。此时如果待添加节点为红色添加第一个节点为红色违背了第二条规则根节点必须是黑色。再添加第二个节点18此时满足红黑树的五大规则无需调整。再添加第三个节点23仍旧满足红黑规则无需调整。由上述例子可知如果默认节点为红色添加三个节点要调整一次。因此添加节点默认是红色的效率最高。2.添加规则在上面的基础上加一些难度现在要添加第四个节点22步骤是这样的1、发现违背了红色不能相连的规则。2、添加节点非根 - 父节点是红色 - 叔节点为红色3、将父节点设置为黑再将叔叔节点设置为黑祖父设为红。4、祖父节点为根节点需要再变回黑色总结红黑树之所以比 AVL 树增删快就是因为它在冲突时优先选择变色哪怕需要旋转通常最多也只需要 3 次旋转就能搞定而 AVL 树的旋转次数是不可控的。