数据结构学习，2-3树与红黑树（java语言）
- 1.‘2-3’树
-
- 1.1 什么是‘2-3树’
- 1.2 ‘2-3树’如何保持绝对平衡？
- 2.红黑树
-
- 2.1红黑树的性质
- 2.2红黑树与‘2-3’树的等价关系
- 2.3左旋转
- 2.4flipColors(颜色翻转)
- 2.5右旋转
- 2.6左旋转、右旋转、颜色翻转的关联性
- 2.7向红黑树中添加节点
- 3.红黑树的复杂度分析
- 4.总结
1.‘2-3’树
1.1 什么是‘2-3树’
2-3树是一种绝对平衡的树，一颗2-3树种有二节点与三节点的树结构
1.2 ‘2-3树’如何保持绝对平衡？
对2-3树保持绝对平衡的方法，我们先看一下如何在2-3树种添加元素
首先我们在空树中添加一个节点，那么这个节点毫无疑问是根节点，并且是个2节点，现在，如果我们再添加一个节点进去会怎么样呢？
如上图，我们将7这个元素加入2-3树中，在之前的二分搜索树中，我们会将7放入根节点的右子树中，这样无法保持树的绝对平衡，在2-3树中，我们是无法向空节点添加元素的，所以元素会和2节点组合成一个3节点
然后我们再向其中添加元素
由于我们不能向空节点中添加元素，所以我们同样，元素1先与我们的根节点组合，由于此时的根节点已经是一个3节点，而2-3树中没有4节点，所以我们先组成一个临时的4节点
此时的根节点不符合2-3树的定义，所以我们要将此时的4节点进行拆分操作，使其成为三个2节点
这样就又满足了2-3树的定义，此时我们再向其中添加元素
11比3大，由二分搜索树的性质，要向其右子树中添加，11又比7大，又要向其右子树中添加，右子树为空，由2-3树的性质，不能向空节点添加元素，所以与7这个2节点组合成一个3节点
此时我们再向其添加元素
根据之前的操作我们应该很容易知道如何添加了
此时我们的2-3树就不平衡了，要怎么办呢？我们再做一个操作将元素11所在的节点与元素3所在的节点组合成一个3节点就可以了
2-3树就是不断进行这样的操作来维持它的绝对平衡性
2.红黑树
2.1红黑树的性质
- 红黑树的节点要么是红色要么是黑色
- 红黑树的根节点是黑色的
- 每个叶子节点（NIL空节点也算）都是黑色的
- 每个红色节点的左右孩子节点都是黑色的
- 从任意一个节点到其所有叶子节点所经过的黑色节点树是一样多的（黑平衡）
2.2红黑树与‘2-3’树的等价关系
红黑树其实就是2-3树的二分搜索树表示，其中红色的节点与其父亲节点组合形成3节点，没有红色孩子节点的节点就是2节点
例如这颗红黑树中，这个红色的节点与其父节点（元素11所在的节点）组成一个3节点，这颗红黑树等价于以下的2-3树
通过以上的对比，我们可以很容易的发现2-3树与红黑树的等价关系
在代码之中，我们可以用一个boolean型变量color来表示红色节点与黑色节点
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node {
public K key;
public V value;
public Node left, right;
public boolean color;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
color = RED;
}
}
并且我们添加一个私有的辅助函数判断节点的颜色
//判断节点node的颜色
private boolean isRed(Node node){
if(node == null)
return BLACK;
else
return node.color;
}
2.3左旋转
我们向一个只有一个节点的红黑树中添加一个比他大的节点
红黑树要满足二分搜索树的性质，于是添加操作也可以和二分搜索树相同，添加到根节点的右子树中
由于我们的定义，红色节点只能存在于其父节点左子树中，所以我们要进行左旋转
左旋转之后再将节点的颜色做出改变
此时就完成了一个左旋转的过程
我们设置一个私有辅助函数
//左旋转
private Node leftRotate(Node node){
Node x = node.right;
//左旋转
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
我们注意到，颜色翻转的时候我们将x节点的颜色与node节点颜色等价，却将node节点的颜色直接改成红色，为什么不将x节点的颜色直接变成黑色呢？原因很简单，如果我们一开始的node节点的一个红色节点，也能向其中添加红节点，如果我们单纯的直接将x节点变成黑色就出错了
此时元素3所在的节点需要左旋转
此时x节点就不是单纯的黑色了，而是红色，此时就变成了一个3节点，要进行分解操作了
2.4flipColors(颜色翻转)
如果我们这样添加一个元素，红黑树会变成什么样呢？
在红黑树中一个黑色节点的左右孩子都是红色节点就相当于在2-3树中的4-node，需要进行拆分操作，在红黑树中很容易就能进行拆分，只要进行flipColors就可以了
至于元素7所在的节点是否要与其父节点进行其他操作就看父节点的颜色，若是黑色则不需要操作，若是红色则进行右旋转
同样我们设计一个名为flipColors的辅助函数
//颜色翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
2.5右旋转
在2.3的最后我们得到了一个这样的红黑树
这显然对应的是2-3树中的4-node，它不应该存在，所以我们需要用到右旋转将他拆分
旋转之后同左旋转一样，要将x节点的颜色改成原先node节点的颜色，并且将node节点改成红色
这样我们的右旋转就完成了
代码基本与左旋转相反
//右旋转
private Node rightRotate(Node node){
Node x = node.left;
//右旋转
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
此时右旋转之后的红黑树中，节点7的左右孩子的颜色都是红色，因此我们还需要对他进行颜色翻转操作
由于节点7已经是根节点了，因此再将节点7的颜色改变即可
2.6左旋转、右旋转、颜色翻转的关联性
通过上面的例子我们可以看出，在左旋转之后如果原本左旋转的节点的父节点是一个红色节点，就要对其父节点的父节点进行右旋转，然后再对右旋转得到的新的子树根节点进行颜色翻转
2.7向红黑树中添加节点
向红黑树中添加的节点都是红色节点，先用二分搜索树添加节点的方法添加进红黑树，然后再回溯通过以上三种判断（是否需要左旋转、右旋转、颜色翻转），得到新的红黑树，再维护一下根节点，使其永远保持黑色
// 向红黑树中添加新的元素e
public void add(K key, V value) {
root = add(root, key, value);
root.color = BLACK; //最终根节点为黑色节点
}
// 向以node为根的红黑树中插入元素e，递归算法
// 返回插入新节点后红黑树的根
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);//默认插入红色节点
}
if (key.compareTo(node.key) < 0)
node.left = add(node.left, key, value);
else if (key.compareTo(node.key) > 0)
node.right = add(node.right, key, value);
else {
node.value = value;
}
if(isRed(node.right) && !isRed(node.left)){
node = leftRotate(node);
}
if(isRed(node.left) && isRed(node.left.left)){
node = rightRotate(node);
}
if(isRed(node.left) && isRed(node.right)){
flipColors(node);
}
return node;
}
3.红黑树的复杂度分析
红黑树由于是一种黑平衡的数据结构，其平衡性甚至还没有AVL树高，对查询操作时，最大可能遍历的节点数是2logn，而AVL树是logn
4.总结
二分搜索树：
优点：再储存完全随机的数据时很好用；
缺点：极端情况下可能会退化成链表；
AVL树：
优点：对于查询较多的数据，AVL树很好用；
红黑树：
优点：统计性能更优（当进行综合增删改查所有的操作时，用红黑树比较好）
缺点：牺牲了平衡性（2logn的高度）