3.3.1 2-3 查找树
- 2-结点,含有一个键(及其对应的值)和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点。
- 3- 结点,含有两个键(及其对应的值)和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的 2-3 树中的键都大于该结点。
3.3.1.1 查找
3.3.1.2 向 2-结点中插入新键
3.3.1.3 向一棵只含有一个3-结点的树中插入新键
3.3.1.4 向一个父结点为2-结点的3-结点中插入新键
3.3.1.5 向一个父结点为3-结点的3-结点中插入新键
3.3.1.6 分解根结点
3.3.1.7 局部变换
3.3.1.8 全局性质
3.3.2 红黑二叉查找树
2-3树数据结构,用标准的二叉查找树(完全由2-结点构成)和一些额外的信息(替换3-结点)来表示 2-3树
3.3.2.1 替换3-结点
- 红链接:将两个2-结点连接起来构成一个3-结点
- 黑链接:2-3树中的普通链接
3.3.2.2 一种等价的定义
- 红链接均为左链接
- 没有任何一个结点同时和两条红链接相连
- 该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同
3.3.2.3 一一对应
3.3.2.4 颜色表示
3.3.2.5 旋转
3.3.2.6 在旋转后重置父结点的链接
3.3.2.7 向单个2-结点中插入新键
3.3.2.8 向树底部的2-结点插入新键
3.3.2.9 向一棵双键树(即一个3-结点)中插入新键
3.3.2.10 颜色转换
3.3.2.11 根结点总是黑色
3.3.2.12 向树底部的3-结点插入新键
3.3.2.13 将红链接在树中向上传递
3.3.3 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class RedBlackBST<Key extends Comparable<Key>, Value>
{
private Node root;
private class Node // 含有color变量的Node对象(请见3.3.2.4节)
private boolean isRed(Node h)
private Node rotateLeft(Node h)
private Node rotateRight(Node h)
private void flipColors(Node h)
private int size()
public void put(Key key, Value val)
{ // 查找key,找到则更新其值,否则为它新建一个结点
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);
else 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.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
}
|
文章作者
lim
上次更新
2024-09-14
(2aae67a)
许可协议
CC BY-NC-ND 4.0