<img src="https://i.imgur.com/oKdeq5j.jpg" width=800 height=160 /> **2-3树节点**: 1. null节点,null节点到根节点的距离都是相同的,所以2-3数是平衡树 2. 2叉节点,有两个分树,节点中有一个元素,左树元素更小,右树元素节点更大 3. 3叉节点,有三个子树,节点中有两个元素,左树元素更小,右树元素更大,中间树介于两个父元素之间。 ![2叉节点](https://i.imgur.com/rfAJOPK.png) ![3叉节点](https://i.imgur.com/aqNFC10.png) 插入操作如下图所示 ![2-3tree插入操作](https://i.imgur.com/MkuZR33.png)
红黑树可以理解为实现了2-3树的BST(binary search tree),它是一个自平衡树,保证在最坏的情况下的操作也是O(lg(n)) <font color='#FF0000' face='黑体'>特性:</font>
查找操作与BST是相同的 插入规则如下:
操作流程如下图所示:
<img src="https://i.imgur.com/QqrUI06.jpg" width=780 height=450 />
<font color='#FF0000' face='黑体'>左旋:</font>
<img src="https://i.imgur.com/OWUbNFO.jpg" width=330 height=256 /> <img src="https://i.imgur.com/rwYXXvw.jpg" width=300 height=256 />
左图为左旋前,右图为左旋后,代码如下所示:
private Node rotateRight(Node h){ assert isRed(h.right); Node x = h.right; // 复制h的 右子树 为节点x h.right = x.left; // 将x的左子树移动到h的右节点上(替代) x.left = h; // 将修改后的h节点作为x的左节点(替代) x.color = h.color; // x继承h的颜色 h.color = RED; // 将h节点的颜色设置为红色 return x; // 返回x节点作为新的父节点 }
右旋操作与之类似
<font color='#FF0000' face='黑体'>颜色反转:</font>
<img src="https://i.imgur.com/1Rz9ysY.jpg" width=340 height=210 /> <img src="https://i.imgur.com/dCvUf0P.jpg" width=340 height=210 />
左图为颜色翻转前,右图为操作之后,代码如下所示:
private void flipColors(Node h){ assert !isRed(h); assert isRed(h.left); assert isRed(h.right); h.color = RED; // 将父节点颜色改为红色 h.left.color = BLACK; // 将左右子节点颜色改为黑色, h.right.color = BLACK; }
此处只实现了查找与插入,如要完整实现所有功能(还有删除),可以采用**左倾红黑树**(LLRB, Left-leaning red–black tree) 红黑树显示的demo
Reference