树：23树和红黑树

作者: 81bad73e9053 | 来源:发表于2016-10-12 19:29 被阅读1215次

树：23树和红黑树
数据结构与算法-AVL 红黑树
数据结构—树—红黑树
TreeMap
算法+红黑树
红黑树
拿下红黑树
[树]红黑树
红黑树专题
B树和红黑树

23树和红黑树

1. 2-3 查找树

1.1 2-3树定义

Paste_Image.png

2-节点，含有一个键和两条链接。
3-节点，含有两个键和三条链接
一棵完美平衡的2-3树中所有空链到根节点的距离都应该是相同的。

1.2 2-3树的查找过程

判断一个键是否在树中，先将它和根节点中的键比较，如果它和其中任何一个键相等，则查找命中，否则我们就根据比较的结果来找到指向相应区间的链接，并在指向的子树中递归的进行查找，如果这是个空链接，则查找未命中。

1.2.1 对H的命中查找

Paste_Image.png

1.2.2 对B的未命中查找

Paste_Image.png

在AC的中间所指的链去查找，是空链，未命中

1.3 插入

首先进行一次未命中查找，然后将新键插入到树的底部，之所以采取2-3树，是因为这样能够保持平衡，下面来分析如何保持平衡

1.3.1 向2-节点插入新键

如果是向一个2节点插入新建，直接变成3-节点，所有空链到根节点的高度不变。

插入K的过程

K<L,所以去L的左子树中去查找，L的左子树是空，所以未命中，将K插入，把包含L节点的2-节点直接变成3-节点

Paste_Image.png

1.3.2 向一颗只含有3-节点的树种插入新键

Paste_Image.png

1.3.3 向一个父节点是2-节点的3-节点插入新键：插入Z

假设未命中查找结束于一个3-节点，而且该3-节点的父节点是2-节点。我们的做法是新键一个4-节点，并将4-节点分解，其中，中键移动到原来的父节点中，也就是原来的2-节点变成3-节点。

Paste_Image.png

1.3.4 向一个父节点是3-节点的3-节点插入新键：插入D

假设未命中查找结束于一个3-节点，而且该3-节点的父节点是3-节点。我们的做法是新键一个4-节点，并将4-节点分解，其中，中键移动到原来的父节点中，也就是原来的3-节点变成4-节点，然后再进行一次分解，一直向上，直到碰到一个2-节点，或者3-节点的根节点。

Paste_Image.png

1.4 局部变换

4-节点变成2-3节点，不会影响树的平衡性。

4-节点的分解.png

Paste_Image.png

1.5 2-3树的生长轨迹

1.png

2.png

2.红黑树

2.1定义

1.红链接均为左链接
2.没有任何一个节点同时和两条红链接相连
3.该树是完美黑平衡的，即任意空链接到根节点上的黑链接数量相同
红链接：将两个2-节点连接起来构成3-节点
黑链接：2-3树种的普通链接

由一条红色左链接相连的2-节点表示一个3-节点.png

2.2 一一对应

如果我们将由红链接相连的节点合并，得到的就是一颗2-3树，相反如果把2-3树中的3-节点画作由红色左链接相连的两个2-节点，那么不会存在和两条红链接相连的节点同时树必然是完美黑平衡的。

红黑树和2-3树的一一对应关系.png

2.3 颜色表示

每个节点都有一条由父节点指向自己的链接，用bool变量来表示链接的颜色，约定空链接的颜色是黑色。

链接的颜色.png

private static final boolean RED = true;
private static final boolean BLACK = false;

public class Node { 

    Key key;//键
    Value value;//值
    Node left,right;//左右节点
    boolean color;//父链接指向自己的链接的颜色
    int N;//节点数
    
    Node(Key key,Value value,int N,boolean color){
        this.key = key;
        this.value = value;
        this.N = N;
        this.color = color;
    } 
}

public boolean isRed(Node x){
    if(x == null) return false;//空链接为黑色
    return x.color;
}