[摘自算法(第4般)]
2-3 查找树
定义
一棵2-3查找树为一棵空树或者由以下节点组成:
2-节点, 含有一个键和2条边,左边指向的2-3树中的键都小于这个键,右键指向的2-3树种的键都大于这个键。
3-节点, 含有2个键3条边,左边指向的2-3树小于小键,中边指向2-3树的键大于小键小于大键,右边指向的2-3树的键大于大键。
示例如下:
查找算法和普通BST类似
主要看插入算法
插入
向2-节点中插入新键
直接把2-节点变成3-节点即可。如图:
向一棵只含有3-节点的树中插入新键
把新键存入这个3-节点,使之称为4-节点,然后把转化成3个2-节点。如图:
向一个父节点为2-节点的3-节点插入新键
把新键存入这个3-节点,使之称为4-节点,但此时不会为中键创建新节点,而是将其移动至父亲节点中。
向一个父节点为3-节点的3-节点插入新键
把新键存入这个3-节点,使之称为4-节点,将其移动至父亲节点中,但是父亲节点又成了4-节点,然后接着往上操作,直到遇到一个2-节点,或者是遇到3-节点的根。
如果是遇到了3-节点的根,则可以按照方法:向一棵只含有3-节点的树中插入新键。将其变成4-节点然后分解。注意:此时树的高度加一。
局部变换不影响全局性质
将一个4-节点分解成2-3树可能有6种情况,但是不论怎么变都不会改变全局的有序性和平衡性。
变换之前空链到根节点的长度为h,变换之后还是h(除了分解那个会变成h+1)
红黑二叉查找树
定义
红黑二叉查找树背后的思想是使用标准的二叉查找树(全是2-节点构成的)和一些额外信息。
我们将树中的连接(边)分成2种类型:
- 红链接将两个2-节点连接起来构成3-节点
- 黑链接则是2-3中的普通连接
也就是我们把3-节点表示成一条左斜的红色连接。如图:(粗边表示红连接)
对于任何2-3树,只要进行进行节点转换,我们就可以派生出来对应的二叉查找树。我们把这种方式表示的二叉查找树称为红黑二叉查找树(红黑树)。
另外一种等价的定义是:
含有红黑连接并满足下列条件的二叉查找树:
- 红链接均为左连接
- 没有任何一个结点同时和2条红连接相连
- 该树是完美黑色平衡的,即任意空连接到根节点的路径上的黑连接数量相同
性质:
一棵大小为N的红黑树的高度不会超过2lgN。
证明:红黑树的最坏情况是它对应的2-3树中构成的最左边路径全都是3-节点,其余均为2-节点。此时最左边路径长度为只包含2-节点的2倍(lgn)。
颜色表示:
把连接的颜色保存在Node中的color中。如果指向它的连接时红色的,该变量为true,黑色则为false。当我们提到一个结点的颜色的时候指的是指向该结点连接的颜色。
注意:约定空节点为黑色。
部分代码:
static final boolean RED = true; static final boolean BLACK = false; Node root; private class Node { int value; Node left, right; int n; boolean color; Node(int value, int n, boolean color) { this.value = value; this.n = n; this.color = color; } } boolean isRed(Node x) { if (x == null) { return false; } return x.color == RED; }
旋转
左旋:
右旋:
旋转会返回一个连接,可能是黑的,也可能是红的,所以我们将用x.color=h.color保留原连接的红黑状态。部分代码如下:
Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.n = h.n; // h.n = 1 + size(h.left) + size(h.right); return x; } Node rotateRight(Node h) { Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; x.n = h.n; // h.n = 1 + size(h.left) + size(h.right); return x; }
插入
向单个2-节点插入新键
(新增的一定是红色节点,这样可以尽可能保证黑色平衡)
如果新键小于老键,新增一个红色节点即可(即指向新键的红链),如果新键大于老键,新增的红色节点将产生右链,不满足条件,需要将老键进行左旋:root = rotate(root)
,如图:
向3-节点插入新建
可以分为3种子情况:
- 新键大于原树中的2个键。这样中间的那个键就会有2条红边,直接把2条红边变黑,然后中间那个节点变红(根节点除外)。如图左1。
- 新键小于原树中的2个键。会产生两个相连的左红连接,需要右旋,然后变色。如图左2.
- 新键位于原树2个件之间。会产生一个左红连接和右红连接相连。需要先左旋变成情况2,然后右旋变成情况1,然后变色。如图左3。
颜色变换的时候需要将父节点的颜色由黑变红。这样是为了不影响整棵树的黑色平衡性。
变色之后呢?红链将向上传递。
总结:
插入之后:
- 如果右子节点是红色的而左子节点是黑色的则左旋,
- 如果左子节点是红的且左子节点的左子节点也是红的,则右旋。
- 如果左右节点均为红色,则颜色转换。
代码实现
package demo; /** * @author TylerChen * @date 2021/3/1 - 21:39 */ public class RedBlackTree { static final boolean RED = true; static final boolean BLACK = false; Node root; private class Node { int value; Node left, right; int n; boolean color; Node(int value, int n, boolean color) { this.value = value; this.n = n; this.color = color; } } boolean isRed(Node x) { if (x == null) { return false; } return x.color == RED; } Node rotateLeft(Node h) { Node x = h.right; h.right = x.left; x.left = h; x.color = h.color; h.color = RED; x.n = h.n; // h.n = 1 + size(h.left) + size(h.right); return x; } Node rotateRight(Node h) { Node x = h.left; h.left = x.right; x.right = h; x.color = h.color; h.color = RED; x.n = h.n; // h.n = 1 + size(h.left) + size(h.right); return x; } void flipColors(Node h) { h.color = RED; h.left.color = BLACK; h.right.color = BLACK; } void put(int value) { root = put(root, value); root.color = BLACK; } //从下往上传递,要使用后序遍历 Node put(Node h, int value) { if (h == null) { return new Node(value, 1, RED); } if (value < h.value) { h.left = put(h.left, value); } else if (value > h.value) { h.right = put(h.right, value); } if(isRed(h.right) && !isRed(h.left)){ h = rotateLeft(h); } if(isRed(h.left) && isRed(h.left.left)){ h = rotateRight(h); } if(isRed(h.left) && isRed(h.right)){ flipColors(h); } // h.n = 1 + size(h.left) + size(h.right); return h; } }