平衡查找树

  1. 2–3查找树
2-结点,含有一个键和两条链接,左链接指向的2–3树中的键都小于该结点,右链接指向的2–3树中的键都大于该结点。
3-结点,含有两个键和三条链接,左链接指向的2–3树中的键都小于该结点,中链接指向的2–3树中的键都位于该结点的两个键之间,右链接指向的2–3树中的键都大于该结点。

· 如果未命中的查找结束于一个2-结点,只要把这个2-结点替换为一个3-结点,将要插入的键保存在其中即可。

· 向3-结点中插入新键:分解4-结点。

在一棵大小为N的2–3树中,查找和插入操作访问的结点必然不超过lgN个。

2. 红黑二叉查找树

红链接将两个2-结点连接起来构成一个3-结点,黑链接则是2–3树中的普通链接。提到一个结点的颜色时,指的是指向该结点的链接的颜色,反之亦然。

红链接均为左链接;没有任何一个结点同时和两条红链接相连;该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同。

左(右)旋转:将用两个键中的较小(大)者作为根结点变为较大(小)者作为根结点。

向单个2-结点中插入新键:如果新键小于老键,只需要新增一个红色的结点;如果新键大于老键,那么新增的红色结点将会产生一条红色的右链接,需要进行左旋转。

向一个3-结点中插入新键:新键大于原树中的两个键→将两条链接的颜色都由红变黑;新键小于原树中的两个键→将上层的红链接右旋转即可得到第一种情况;新键介于原树中的两个键之间→将下层的红链接左旋转即可得到第二种情况。

总结来说,在沿着插入点到根结点的路径向上移动时在所经过的每个结点中顺序完成以下操作,就能完成插入操作:

· 如果右子结点是红色的而左子结点是黑色的,进行左旋转;

· 如果左子结点是红色的且它的左子结点也是红色的,进行右旋转;

· 如果左右子结点均为红色,进行颜色转换。

public class RedBlackBST<Key extends Comparable<Key>, Value>
{
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node
{
Key key;
Value val;
Node left, right;
int N;
boolean color;
Node(Key key, Value val, int N, boolean color)
{
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}
private 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;
}
public void put(Key key, Value val)
{
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val)
{
if(h == null) return new Node(key, val, 1, RED);
int cmp = key.compareTo(h.key);
if(cmp < 0) h.left = put(h.left, key, val);
if(cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
if(isRed(h.right)&&!isRed(h.left)) h = rotateLeft(h);
if(isRed(h.left)&&isRed(h.right)) h = rotateRight(h);
if(isRed(h.right)&&isRed(h.left)) flipColors(h);
h.N = size(h.right) + size(h.left) + 1;
return h;
}
}
所有基于红黑树的符号表实现都能保证操作的运行时间为对数级别。
One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.