高级数据结构---红黑树及其插入左旋右旋代码java实现
白露非霜 人气:1前面我们说到的二叉查找树，可以看到根结点是初始化之后就是固定了的，后续插入的数如果都比它大，或者都比它小，那么这个时候它就退化成了链表了，查询的时间复杂度就变成了O(n),而不是理想中O(logn),就像这个样子
如果我们有一个平衡机制，让这棵树可以动起来，比如将4变成根结点，是不是查询效率又可以提高了，这就要提到另外一种特殊的二叉树---红黑树（也是一种特殊的二叉查找树）。JDK1.8中将HashMap底层实现的数据结构由数组+链表变成了数组+链表+红黑树。当链表长度超过8就转换成红黑树，明显红黑树的查找效率是高于链表的吧。
红黑树的特点：
1.每个结点不是红色就是黑色
2.不可能有连在一起的红色结点（黑色的就可以），每个叶子节点都是黑色的空节点（nil），也就是说，叶子节点不存储数据
3.根结点都是黑色 root
4.每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
5.新插入的元素都是红色，根除外
因为红黑树要满足以上特点，所以就有变色机制和旋转平衡机制来调节树高度。
变色：
当前节点红色，父结点和叔叔结点都是红色，将父结点和叔叔结点变成黑色，把爷爷结点设置成红色；只有父结点是红色，那就将父结点变黑色，爷爷结点变红色。完成变色之后进行左旋/右旋。
注：下面的当前节点都是变化后的操作结点。
左旋：变完色之后将操作结点变成爷爷结点，以其爷爷结点去旋转。
条件：当前结点（爷爷结点）父结点是红色，叔叔是黑色，且当前结点是右子树。
操作结点指向父结点，将当前结点（变色前结点的太爷爷）右孩子的左孩子变成其右孩子，当前结点变成其右孩子的左孩子，其右孩子填补当前结点位置
右旋：
条件：当前结点父结点是红色，叔叔是黑色，且当前结点是左子树。
父结点变成黑色，爷爷变成红色（这个变色就是上面的第二种变色），以太爷爷为操作结点右旋。将其左孩子的右子树变成其左子树，将当前结点变成其左孩子的右子树。其做孩子填补当前位置。
左旋右旋动图：
代码实现：真心的太抽象了，看起来简单，代码实现起来，各种结点的引用指向太乱了；下面的代码几乎每一行都写了注释，尤其是左旋和右旋
package com.nijunyang.algorithm.tree;
/**
* Description: 红黑树
* Created by nijunyang on 2020/4/20 20:23
*
* 红黑树的性质：
* 1.每个结点不是红色就是黑色
* 2.不可能有连在一起的红色结点（黑色的就可以），每个叶子节点都是黑色的空节点（nil），也就是说，叶子节点不存储数据
* 3.根结点都是黑色 root
* 4.每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点
* 5.新插入的元素都是红色，根除外
*/
public class RedBlackTree {
private Node root = Node.nil;
public static void main(String[] args){
RedBlackTree redBlackTree = new RedBlackTree();
//19,5,30,1,12,35,7,13,6
redBlackTree.insert(19);
redBlackTree.insert(5);
redBlackTree.insert(30);
redBlackTree.insert(1);
redBlackTree.insert(12);
redBlackTree.insert(35);
redBlackTree.insert(7);
redBlackTree.insert(13);
redBlackTree.insert(6);
RedBlackTree.inOrderTraversal(redBlackTree);
System.out.println();
}
public <T extends Comparable<T>> void insert(T data){
Node<T> temp = root;
Node<T> node = new Node<>(data);
if (root == Node.nil) {
root = node;
node.parent.parent = Node.nil;
}
else {
node.black = false;
//插入
while (true) {
if (temp.data.compareTo(data) < 0) {
if (temp.rightChild == Node.nil) {
temp.rightChild = node;
node.parent = temp;
break;
} else {
temp = temp.rightChild;
}
}
else if (temp.data.compareTo(data) == 0) {
//等于保留原来数据
return;
}
else {
if (temp.leftChild == Node.nil) {
temp.leftChild = node;
node.parent = temp;
break;
} else {
temp = temp.leftChild;
}
}
}
//变色和旋转
fixTree(node);
}
}
private static void inOrderTraversal(RedBlackTree redBlackTree) {
TreeUtil.inOrderTraversal(redBlackTree.root);
}
/**
* 变色和旋转
* @param node
* @param <T>
*/
private <T extends Comparable<T>> void fixTree(Node<T> node) {
/**
* 1.变色 条件：父结点及叔叔结点都是红色，变色过程：把父结点和叔叔结点都变成黑色，把爷爷设置成红色，指针指向爷爷结点
* 2.左旋：上一步将指针指向了爷爷结点.条件：当前结点（爷爷结点）父结点是红色，叔叔是黑色，且当前结点是右子树。进行左旋：
* 临时指针指向父结点，将当前结点（变色前结点的太爷爷）右孩子的左孩子变成其右孩子，当前结点变成其右孩子的左孩子，
* 其右孩子填补当前结点位置
*
* 3.右旋：条件：当前结点父结点是红色，叔叔是黑色，且当前结点是左子树。进行右旋：
* 父结点变成黑色，爷爷变成红色，以太爷爷为点右旋。将其左孩子的右子树变成其左子树，将当前结点变成其左孩子的右子树。其做孩子填补当前位置
*
*/
Node<T> currentNode = node;
while (!currentNode.parent.black) {
Node<T> temp;
if (currentNode.parent == currentNode.parent.parent.leftChild) { //当前父结点是左孩子
temp = currentNode.parent.parent.rightChild; //叔叔结点
//变色
if (temp != Node.nil && !temp.black) { //叔叔也是红色，将父和叔叔都变黑色
currentNode.parent.black = true;
temp.black = true;
currentNode.parent.parent.black = false; //爷爷变成红色
currentNode = currentNode.parent.parent; //变色完成指向爷爷
continue; //进入下一次循环判断爷爷的位置是否也需要变色，直到不变满足变色了才开始左旋/右旋
}
if (currentNode == currentNode.parent.rightChild) { //当前结点是右子树
currentNode = currentNode.parent; //以其父结点进行左旋
//左旋
leftRotate(currentNode);
}
//右旋
//父结点变成黑色，爷爷变成红色,准备右旋
currentNode.parent.black = true;
currentNode.parent.parent.black = false;
//指针指向太爷爷去右旋
currentNode = currentNode.parent.parent;
rightRotate(currentNode);
}
else { //当前父结点是右孩子
temp = currentNode.parent.parent.leftChild;
if (temp != Node.nil && !temp.black) {
currentNode.parent.black = true;
temp.black = true;
currentNode.parent.parent.black = false;
currentNode = currentNode.parent.parent;
continue;
}
if (currentNode == currentNode.parent.leftChild) {
currentNode = currentNode.parent;
rightRotate(currentNode);
}
//父结点变成黑色，爷爷变成红色,准备左旋
currentNode.parent.black = true;
currentNode.parent.parent.black = false;
//指针指向太爷爷去左旋
currentNode = currentNode.parent.parent;
leftRotate(currentNode);
}
}
root.black = true; //根结点始终黑色
}
/**
* 左旋：将其右孩子的左孩子变成其右孩子，当前结点变成其右孩子的左孩子，其右孩子填补当前结点位置
* @param node
* @param <T>
*/
private <T extends Comparable<T>> void leftRotate(Node<T> node) {
Node <T> currentNode = node;
if (currentNode.parent != Node.nil) {
if (currentNode == currentNode.parent.leftChild) { //当前结点是其父的左孩子
currentNode.parent.leftChild = currentNode.rightChild; // 将其右孩子变成其父的左孩子（右孩子填补当前结点位置）
}
else {
currentNode.parent.rightChild = currentNode.rightChild; //将其右孩子变成其父的右孩子（右孩子填补当前结点位置）
}
currentNode.rightChild.parent = currentNode.parent; //修改其右孩子的父指针，移向其父（右孩子填补当前结点位置）
currentNode.parent = currentNode.rightChild; //当前结点变成其右孩子的孩子
if (currentNode.rightChild.leftChild != Node.nil) {
currentNode.rightChild.leftChild.parent = currentNode; //当前结点右孩子的左孩子变成当前结点的孩子，修改父指针
}
currentNode.rightChild = currentNode.rightChild.leftChild; //当前结点右孩子的左孩子变成当前结点的右孩子
currentNode.parent.leftChild = currentNode; //当前结点新的父亲（以前它的右孩子）的左孩子指向当前节点
}
else { //根就是当前结点
Node right = root.rightChild;
root.rightChild = right.leftChild; //将其右孩子的左孩子变成其右孩子
right.leftChild.parent = root; //修改对应的父指向
root.parent = right;
right.leftChild = root; //当前结点变成其右孩子的左孩子
right.parent = Node.nil;
root = right; //右孩子填补当前位置
}
}
/**
* 右旋：父结点变成黑色，爷爷变成红色,准备右旋。将其左孩子的右子树变成其左子树，将当前结点变成其左孩子的右子树。其左孩子填补当前位置，
* 最后当前节点变成其
* @param node node
* @param <T>
*/
private <T extends Comparable<T>> void rightRotate(Node<T> node) {
Node <T> currentNode = node;
if (currentNode.parent != Node.nil) {
if (currentNode == currentNode.parent.leftChild) { //判断当前结点是其父的左/右结点，其左孩子填补当前位置
currentNode.parent.leftChild = currentNode.leftChild;
} else {
currentNode.parent.rightChild = currentNode.leftChild;
}
currentNode.leftChild.parent = currentNode.parent; //其左孩子填补当前位置，左孩子父指针指向其父指针
currentNode.parent = currentNode.leftChild; //当前结点变成其左孩子的子树
if (currentNode.leftChild.rightChild != Node.nil) {
currentNode.leftChild.rightChild.parent = currentNode; //将其左孩子的右子树变成其左子树
}
currentNode.leftChild = currentNode.leftChild.rightChild; //将其左孩子的右子树变成其左子树
currentNode.parent.rightChild = currentNode; //当前结点新的父亲（以前它的左孩子）的右孩子指向当前节点
} else { //当前结点是根结点
Node<T> left = root.leftChild;
root.leftChild = root.leftChild.rightChild; // 将其左孩子的右子树变成其左子树
left.rightChild.parent = root;
root.parent = left;
left.rightChild = root; //将当前结点变成其左孩子的右子树
left.parent = Node.nil;
root = left; //左孩子填补当前位置
}
}
private static class Node<T extends Comparable<T>> extends TreeNode<T> {
private static final Node nil = new Node<>(null);
T data;
Node<T> parent = nil;
Node<T> leftChild = nil;
Node<T> rightChild = nil;
boolean black = true; //默认黑色
public Node(T data) {
this.data = data;
}
@Override
public T getData() {
return data;
}
@Override
public void setData(T data) {
this.data = data;
}
@Override
public Node<T> getLeftChild() {
return leftChild;
}
public void setLeftChild(Node<T> leftChild) {
this.leftChild = leftChild;
}
@Override
public Node<T> getRightChild() {
return rightChild;
}
public void setRightChild(Node<T> rightChild) {
this.rightChild = rightChild;
}
@Override
public String toString() {
return "data=" + data;
}
}
}
中序遍历的代码：
/**
* 二叉树中序遍历 左子树 根 右子树
* @param node 二叉树节点
*/
public static<N extends TreeNode<T>, T> void inOrderTraversal(N node){
if(node == null){
return;
}
//先找左再输出根,再去找右
inOrderTraversal(node.getLeftChild());
if (node.getData() != null) {
System.out.print(node.getData());
System.out.print(" ");
}
inOrderTraversal(node.getRightChild());
}
TreeNode:
public class TreeNode<T> {
protected T data;
protected TreeNode<T> leftChild;
protected TreeNode<T> rightChild;
public TreeNode() {
}
}
在 https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 上面验证了下插入代码的运行结果和这儿的图解结果是一致的。19,5,30,1,12,35,7,13,6
因为红黑树通过变色和左旋/右旋机制使得个子树的高度尽量平衡，所以他的查询效率是O(logn)。其插入和删除也是近似O(logn).
加载全部内容