使用红黑树进行数据检索
2019-09-28 本文已影响0人
ruoshy
一、概述
当业务中需要对一些数据进行检索，使用常规的遍历查找是非常耗时的，有一种方法是实现二叉查找树，但是二叉查找树在一种极端的情况下会变成链表，失去快速查找的优势变成遍历查找，这个时候我们可以将二叉查找树改造成 —— 红黑树。
二、什么是红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。
三、构建红黑树的条件
- 性质1. 节点是红色或黑色。
- 性质2. 根节点是黑色。
- 性质3. 每个叶结点，即空结点（NIL）是黑的
- 性质4. 每个红色节点的两个子节点都是黑色，不能有连续的红节点。
- 性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
四、保持自平衡的机制
红黑树通过对节点进行变色、左旋、右旋来满足他的性质，达到自平衡的效果。
为了方便修正，父节点默认为黑，每次插入的子节点为红。
例1
红黑树的插入修正有以下几种情况：
父节点、叔节点为红 （图 例1）
- 若子节点、父节点、叔节点为红色，将祖父节点变为红色，父节点和叔节点变为黑色，再以祖父节点为当前节点，判断是否仍然符合修正条件。
父节点为红，叔节点为黑
-
当前节点处于父节点左边，父节点处于祖父节点左边（Left-Left） ，对祖父节点进行右旋，设置祖父节点为红色，父节点为黑色。
-
当前节点处于父节点右边，父节点初一祖父节点左边（Right-Left），对父节点进行左旋，使之符合（Left-Left）条件，执行其操作。
-
当前节点处于父节点右边，父节点处于祖父节点右边（Right-Right），对祖父节点进行左旋，修改父节点为红色，父节点为黑色。
-
当前节点处于父节点左边，父节点处于祖父节点右边（Left-Right），对父节点进行右旋，使之符合（Right-Right）条件，执行其操作。
左旋
对节点 E 左旋
右旋
对节点 S 右旋
五、代码实现
public class RBTree {
class TreeNode {
private TreeNode leftNode;
private TreeNode parentNode;
private TreeNode rightNode;
private Integer color;
private Integer data;
}
// 根节点
private TreeNode treeNode;
public RBTree() {
treeNode = new TreeNode();
}
public void insert(Integer data) {
if (treeNode.data == null) {
treeNode.data = data;
treeNode.color = 0;
} else {
insert(treeNode, data);
}
}
public void insert(TreeNode node, Integer data) {
TreeNode temp = new TreeNode();
temp.color = 1;
temp.data = data;
while (node != null) {
if (node.data > data) {
if (node.leftNode == null) {
temp.parentNode = node;
node.leftNode = temp;
break;
} else {
node = node.leftNode;
}
} else {
if (node.rightNode == null) {
temp.parentNode = node;
node.rightNode = temp;
break;
} else {
node = node.rightNode;
}
}
}
// 修正
revise(temp);
}
public void revise(TreeNode node) {
TreeNode parentNode = node.parentNode;
if (parentNode != null && parentNode.color == 1) {
TreeNode grandfatherNode = parentNode.parentNode;
TreeNode uncleNode = null;
// 获取叔节点
if (grandfatherNode != null) {
uncleNode = grandfatherNode.leftNode == parentNode ? grandfatherNode.rightNode
: grandfatherNode.leftNode;
} else {
parentNode.color = 0;
return;
}
// 若叔节点为黑（null也算黑）
if (uncleNode != null && uncleNode.color == 1) {
// 将父节点、叔节点变黑
parentNode.color = 0;
uncleNode.color = 0;
// 将祖父节点变红，再次修正
grandfatherNode.color = 1;
revise(grandfatherNode);
} else {
// 当前节点在父节点的左边
if (parentNode.leftNode == node) {
// 父节点在祖父节点的左边（Left-Left）
// g f
// f --> n g
// n
if (grandfatherNode.leftNode == parentNode) {
// 对祖父节点进行右旋，并变色
// 黑
// 红 红
rotateRight(grandfatherNode);
parentNode.color = 0;
node.color = 1;
grandfatherNode.color = 1;
}
// 父节点在祖父节点的右边（Left-Right）
// g g
// f --> n
// n f
else {
// 父节点右旋，使其符合（Left-Left），再次修正
rotateRight(parentNode);
revise(parentNode);
}
}
// 当前节点在父节点的右边
else {
// 父节点在祖父节点的左边（Right-Left）
// g g
// f --> n
// n f
if (grandfatherNode.leftNode == parentNode) {
// 父节点左旋，使其符合（Right-Right），再次修正
rotateLeft(parentNode);
revise(parentNode);
}
// 父节点在祖父节点的右边（Right-Right）
// g f
// f --> g n
// n
else {
// 对祖父节点进行左旋，并变色
// 黑
// 红 红
rotateLeft(grandfatherNode);
parentNode.color = 0;
node.color = 1;
grandfatherNode.color = 1;
}
}
}
}
}
public void rotateLeft(TreeNode node) {
TreeNode parentNode = node.parentNode;
TreeNode rightNode = node.rightNode;
// 判断当前节点位于父节点的方向,并将右节点位置移到当前节点位置
if(parentNode != null) {
// 当前节点位于父节点左边
if(parentNode.leftNode == node) {
parentNode.leftNode = rightNode;
}
// 当前节点位于父节点右边
else {
parentNode.rightNode = rightNode;
}
} else {
// 若父节点为空必定是根节点，设置根节点
this.treeNode = rightNode;
}
rightNode.parentNode = parentNode;
// 将右节点的左节点交给当前节点的右节点
node.rightNode = rightNode.leftNode;
if(rightNode.leftNode != null) {
rightNode.leftNode.parentNode = node;
}
// 将当前节点交给右节点的左节点
rightNode.leftNode = node;
node.parentNode = rightNode;
}
public void rotateRight(TreeNode node) {
TreeNode parentNode = node.parentNode;
TreeNode leftNode = node.leftNode;
// 判断当前节点位于父节点的方向,并将左节点位置移到当前节点位置
if(parentNode != null) {
// 当前节点位于父节点左边
if(parentNode.leftNode == node) {
parentNode.leftNode = leftNode;
}
// 当前节点位于父节点右边
else {
parentNode.rightNode = leftNode;
}
} else {
// 若父节点为空必定是根节点，设置根节点
this.treeNode = leftNode;
}
leftNode.parentNode = parentNode;
// 将左节点的右节点交给当前节点的左节点
node.leftNode = leftNode.rightNode;
if(leftNode.rightNode != null) {
leftNode.rightNode.parentNode = node;
}
// 将当前节点交给左节点的右节点
leftNode.rightNode = node;
node.parentNode = leftNode;
}
/**
* 中序遍历
*/
public void middle() {
middle(treeNode);
}
public void middle(TreeNode node) {
// 定义栈
Stack<TreeNode> stack = new Stack<>();
// 直到节点为空且栈为空停止循环
while (node != null || !stack.isEmpty()) {
while (node != null) {
// 将左节点顺序入栈
stack.push(node);
node = node.leftNode;
}
// 取出栈顶元素
node = stack.pop();
// 输出节点元素
System.out.println(node.data + " "+node.color);
// 获取该栈顶元素的右节点并继续将其全部左节点入栈
node = node.rightNode;
}
}
public void search(Integer data) {
search(treeNode, data);
}
public void search(TreeNode node, Integer data) {
int num = 1;
while (node != null) {
num++;
if (node.data.equals(data)) {
System.out.println("查询结果：" + node.data);
break;
} else if (node.data > data) {
node = node.leftNode;
} else {
node = node.rightNode;
}
}
System.out.println("查询比较次数: "+num);
}
}
测试类
public class Test {
public static void main(String[] args) {
RBTree tree = new RBTree();
long start = System.currentTimeMillis();
for (int i = 1; i < 100000; i++) {
tree.insert(i);
}
tree.insert(932145);
System.out.println("插入十万条数据，耗时：" + (System.currentTimeMillis() - start));
start = System.currentTimeMillis();
tree.search(932145);
System.out.println("查询耗时：" + (System.currentTimeMillis() - start));
}
}
⚠️ 以下为对树顺序插入 1 到 100000 的整型数据测试结果
不使用红黑树插入、查询测试
二叉查找树
使用红黑树插入、查询测试
红黑树
通过测试我们发现普通的二叉树插入非常的耗时，查询由于比较的次数过多，耗时比红黑树要长。
六、结论
红黑树通过对树的节点修正，使其不会发生变成链表的情况，充分发挥二叉树的优点，保持各节点子树的平衡。
