概述
《算法导论》中的红黑树的概念
每个节点只能是红色或者黑色根节点都是黑色的每一个叶子节点(还有叶子节点存放的空节点)都是黑色如果一个节点为红色,那么他的孩子节点都为黑色从任意一个节点到叶子节点,经过的黑色节点是一样的(因为红黑树是2-3树的另一种表达方式,2-3树是绝对平衡的,所以红黑树也是一种黑平衡的树)
算法4中的说法
红黑树与2-3树是等价的,同样的红黑树页满足二分搜索数的基本性质
2-3树
特点
一个节点可以存放一个或者两个元素,且可以连接两个或者三个的元素 2-3树是一棵绝对平衡的树(即任意节点的高度差都是0)
2-3树维持平衡示例
如下图所示,按照图中给定元素顺序插入元素,可以看出每当树失衡时,都会将分裂后的节点的父节点向上融合
红黑树与2-3树的关系
如下图所示,红黑树中红色节点就是表示2-3树种三节点的左边的元素
如下图所示,2-3树的树转换为红黑树的样子如下图所示
红黑树的实现
先行步骤
颜色的翻转
图解
如下所示,上图为红黑树相当于对应下方的2-3树的操作,可以看出加入66之后2-3树编程四节点需要向上融合,所以对应红黑树也需要将元素值为42的节点变为红色即与指向一个节点融合为“2节点”。
实现
private void flipColors(Node node
) {
node
.color
= RED
;
node
.left
.color
= BLACK
;
node
.right
.color
= BLACK
;
}
右旋转
图解
如下图所示,一个添加节点后变成不平衡树的红黑树,所以我们需要向右旋转,再更新一下颜色,因为会融合成“4节点”,所以旋转后根节点和原来节点颜色一样,旧的根节点变成红色表示与根节点融合
实现代码
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
;
}
LR型的情况
图解
这种情况和avl树种lr型情况很像,解决方式也很简单,左旋转后再右旋转更新一下颜色即可。需要补充的是,下图已经包含上述先行步骤的所有情况,所以我们只需针对下图情况下三个独立的if即可完成红黑树的添加操作。
实现代码
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
;
}
完整代码
package com
.study
.RBTreeDemo
;
import java
.util
.ArrayList
;
public class RBTree<K
extends Comparable<K>, V
> {
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
;
}
}
private Node root
;
private int size
;
public RBTree() {
root
= null
;
size
= 0;
}
public int getSize() {
return size
;
}
public boolean isEmpty() {
return size
== 0;
}
private boolean isRed(Node node
) {
if (node
== null
)
return BLACK
;
return node
.color
;
}
public void add(K key
, V value
) {
root
= add(root
, key
, value
);
}
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
;
}
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
;
}
private void flipColors(Node node
) {
node
.color
= RED
;
node
.left
.color
= BLACK
;
node
.right
.color
= BLACK
;
}
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
;
}
private Node
getNode(Node node
, K key
) {
if (node
== null
)
return null
;
if (key
.equals(node
.key
))
return node
;
else if (key
.compareTo(node
.key
) < 0)
return getNode(node
.left
, key
);
else
return getNode(node
.right
, key
);
}
public boolean contains(K key
) {
return getNode(root
, key
) != null
;
}
public V
get(K key
) {
Node node
= getNode(root
, key
);
return node
== null
? null
: node
.value
;
}
public void set(K key
, V newValue
) {
Node node
= getNode(root
, key
);
if (node
== null
)
throw new IllegalArgumentException(key
+ " doesn't exist!");
node
.value
= newValue
;
}
private Node
minimum(Node node
) {
if (node
.left
== null
)
return node
;
return minimum(node
.left
);
}
private Node
removeMin(Node node
) {
if (node
.left
== null
) {
Node rightNode
= node
.right
;
node
.right
= null
;
size
--;
return rightNode
;
}
node
.left
= removeMin(node
.left
);
return node
;
}
public V
remove(K key
) {
Node node
= getNode(root
, key
);
if (node
!= null
) {
root
= remove(root
, key
);
return node
.value
;
}
return null
;
}
private Node
remove(Node node
, K key
) {
if (node
== null
)
return null
;
if (key
.compareTo(node
.key
) < 0) {
node
.left
= remove(node
.left
, key
);
return node
;
} else if (key
.compareTo(node
.key
) > 0) {
node
.right
= remove(node
.right
, key
);
return node
;
} else {
if (node
.left
== null
) {
Node rightNode
= node
.right
;
node
.right
= null
;
size
--;
return rightNode
;
}
if (node
.right
== null
) {
Node leftNode
= node
.left
;
node
.left
= null
;
size
--;
return leftNode
;
}
Node successor
= minimum(node
.right
);
successor
.right
= removeMin(node
.right
);
successor
.left
= node
.left
;
node
.left
= node
.right
= null
;
return successor
;
}
}
public static void main(String
[] args
) {
System
.out
.println("Pride and Prejudice");
ArrayList
<String> words
= new ArrayList<>();
if (FileOperation
.readFile("F:\\Red-Black-Tree\\src\\pride-and-prejudice.txt", words
)) {
System
.out
.println("Total words: " + words
.size());
RBTree
<String, Integer> map
= new RBTree<>();
for (String word
: words
) {
if (map
.contains(word
))
map
.set(word
, map
.get(word
) + 1);
else
map
.add(word
, 1);
}
System
.out
.println("Total different words: " + map
.getSize());
System
.out
.println("Frequency of PRIDE: " + map
.get("pride"));
System
.out
.println("Frequency of PREJUDICE: " + map
.get("prejudice"));
}
System
.out
.println();
}
}
总结
若添加的节点值完全随机,二分搜索树最适合不过。若是出现极端情况,二分搜索树极有可能变成链表。
对于查询avl最合适不过。他的平衡高度为logn比红黑树的“黑平衡”那种2logn的平衡要出色很多
若需要增删改查等综合操作,建议使用红黑树,红黑树虽然不是最优但是综合上是最优的