失眠网 > 红黑树插入操作的初步理解

红黑树插入操作的初步理解

时间：2020-04-23 04:16:13

相关推荐

红黑树插入操作的初步理解

文章目录

红黑树插入操作的初步理解红黑树的特征红黑树的插入节点总是红色的红黑树的修正变色左旋右旋插入操作插入操作的代码实现红黑树和AVL树的对比参考链接

红黑树的特征

每个节点不是红色就是黑色的根节点总是黑色的如果节点是红色的，则它的子节点必须是黑色的从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

红黑树的插入节点总是红色的

因为红黑树的特性,如果我们每次插入的节点是黑色的,那么就必然会违背规则4,因为插入一个黑色节点肯定会导致不平衡。

所以新插入的节点会选择红色，这样每次一定会满足条件4，而且只有1/2的几率会违背规则3（只有当新插入节点的父节点是红色的时候才会违背规则3）

红黑树的修正

对于不平衡的红黑树，我们需要进行修正。

修正方法主要有3种：

变色

变色就很好理解，因为违背了规则3，所以需要将节点颜色变换，以达到某种要求

左旋

比如说拿5举例进行左旋操作，会将8代替5的位置，并且会将8的左子树接到5的右子树上（如果存在的话）

右旋

右旋也是同样的道理，对8进行右旋操作，看图理解一下就行

插入操作

具体的来说，对于一个插入操作，如果红黑树不平衡，那么就会是下面6种情况之一

在下面的表述中，

用node称为当前插入的节点

用parent称为node的父节点

用gparent称为parent的父节点

用uncle称为parent的兄弟节点，也就是gparent的另外一个子节点

说明一点，如果parent是黑色的，那么必然是不用调整的，也就是说，调整的前提是父节点是红色的

parent是gparent的左子节点

uncle节点是红色的node节点是parent的右子节点node节点是parent的左子节点

parent是gparent的右子节点

uncle节点是红色的node节点是parent的左子节点node节点是parent的右子节点

可以发现，这6种情况其实可以分为2组，这里只讲述上面三种，下面三种和上面是很类似的，就不再叙述

建立一颗初始化的树

2. 准备插入节点4

发现不平衡，且当前的情况是parent是gparent的左子节点，uncle节点是红色的,也就是上面所列举的情况一。这时就会执行下述操作

将4号节点的parent节点（5）和uncle节点（8）染黑，将gparent（7）染红，并将当前节点（4）跳到gparent（7）

那么，情况就会变成这样,可以发现这就是情况2。

注意，node节点现在已经是7了，不再是4。

4. 对于情况2，会进行如下的调整

将当前node节点的值变为parent的值，也就是node变为（2），并对新的当前节点node（2）进行左旋操作.

树的情况就会变成下图，注意，此时node为2，会发现，这就是情况3

5. 对于情况三，执行如下步骤

将parent节点（7）染黑，gparent节点（11）染红，最后对gparent（11）执行右旋操作即可

6. 经过以上三步，红黑树又重新平衡了。

总的来说，上述的情况一，二，三是连续的，也就是至多3步，就能使红黑树平衡

插入操作的代码实现

/*** @author yiqzq* @date /3/7 11:06* 定义节点*/public class RBNode<T extends Comparable<T>> {boolean red = true;boolean black = false;T value;RBNode<T> parent;RBNode<T> left;RBNode<T> right;public T getValue() {return value;}public RBNode(T value, RBNode<T> parent, RBNode<T> left, RBNode<T> right) {this.value = value;this.parent = parent;this.left = left;this.right = right;}@Overridepublic String toString() {return "RBNode{" +"red=" + red +", black=" + black +", value=" + value +", parent=" + parent +", left=" + left +", right=" + right +'}';}public void setBlack() {this.black = true;this.red = false;}public void setRed() {this.black = false;this.red = true;}public boolean isRed() {return red;}public boolean isBlack() {return black;}}

/*** @author yiqzq* @date /3/7 11:22* @parm insert:新增节点* 红黑树的实现*/public class RBTree<T extends Comparable<T>> {private RBNode<T> root;public void insert(T value) {RBNode<T> node = new RBNode<T>(value, null, null, null);RBNode<T> cur, x;cur = null;x = this.root;while (x != null) {cur = x;int cmp = pareTo(cur.value);//node 小if (cmp < 0) {x = cur.left;} else {x = cur.right;}}node.parent = cur;if (cur == null) {root = node;} else {int cmp = pareTo(cur.value);if (cmp < 0) {cur.left = node;} else {cur.right = node;}}insertFixUp(node);}private void insertFixUp(RBNode<T> node) {RBNode<T> parent, gparent; //定义父节点和祖父节点//父节点存在且父节点为红才需要调整while ((parent = node.parent) != null && parent.isRed()) {gparent = parent.parent;//总共可分为6种情况,父节点是祖父节点的左儿子if (parent == gparent.left) {RBNode<T> uncle = gparent.right;//叔叔节点是红的if (uncle != null && uncle.isRed()) {uncle.setBlack();parent.setBlack();gparent.setRed();node = gparent;continue;}//如果存在这种情况就先左旋if (node == parent.right) {leftRotate(parent);//交换当前节点RBNode<T> tmp = parent;parent = node;node = tmp;}//最后右旋调整红黑树结构parent.setBlack();gparent.setRed();rightRotate(gparent);}//还有相反的三种情况else {RBNode<T> uncle = gparent.left;//叔叔节点为红if (uncle != null && uncle.isRed()) {uncle.setBlack();parent.setBlack();gparent.setRed();node = gparent;continue;}if (node == parent.left) {rightRotate(parent);RBNode<T> tmp = parent;parent = node;node = tmp;}parent.setBlack();gparent.setRed();leftRotate(gparent);}}root.setBlack();}/** 左旋示意图：对节点x进行左旋*p p* / /* x y* / \ / \* lx y-----> x ry* / \ / \* ly rylx ly* 左旋做了三件事：* 1. 将y的左子节点赋给x的右子节点,并将x赋给y左子节点的父节点(y左子节点非空时)* 2. 将x的父节点p(非空时)赋给y的父节点，同时更新p的子节点为y(左或右)* 3. 将y的左子节点设为x，将x的父节点设为y*/private void leftRotate(RBNode<T> x) {RBNode<T> y, gparent;y = x.right;//第一步x.right = y.left;if (y.left != null) {y.left.parent = x;}//第二步y.parent = x.parent;if (x.parent == null) {this.root = y;} else {if (x == x.parent.left) {x.parent.left = y;} else {x.parent.right = y;}}//第三步y.left = x;x.parent = y;}/** 右旋示意图：对节点y进行右旋* p p* / /*y x*/ \ / \* x ry ----->lx y* / \ / \* lx rx rx ry* 右旋做了三件事：* 1. 将x的右子节点赋给y的左子节点,并将y赋给x右子节点的父节点(x右子节点非空时)* 2. 将y的父节点p(非空时)赋给x的父节点，同时更新p的子节点为x(左或右)* 3. 将x的右子节点设为y，将y的父节点设为x*/private void rightRotate(RBNode<T> y) {//1. 第一步RBNode<T> x = y.left;y.left = x.right;if (x.right != null) {x.right.parent = y;}//2.第二步x.parent = y.parent;if (y.parent == null) {this.root = x;} else {if (y == y.parent.right) {y.parent.right = x;} else {y.parent.left = x;}}//3. 第三步x.right = y;y.parent = x;}/** 前序遍历"红黑树"*/private void preOrder(RBNode<T> tree) {if (tree != null) {System.out.print(tree.value + " ");preOrder(tree.left);preOrder(tree.right);}}public void preOrder() {preOrder(root);}/** 中序遍历"红黑树"*/private void inOrder(RBNode<T> tree) {if (tree != null) {inOrder(tree.left);System.out.print(tree.value + " ");inOrder(tree.right);}}public void inOrder() {inOrder(root);}/** 后序遍历"红黑树"*/private void postOrder(RBNode<T> tree) {if (tree != null) {postOrder(tree.left);postOrder(tree.right);System.out.print(tree.value + " ");}}public void postOrder() {postOrder(root);}private void print(RBNode<T> tree, T key, int direction) {if (tree != null) {// tree是根节点if (direction == 0) {System.out.printf("%2d(B) is root\n", tree.value);}// tree是分支节点else {System.out.printf("%2d(%s) is %2d's %6s child\n", tree.value, tree.red ? "R" : "B", key, direction == 1 ? "right" : "left");}print(tree.left, tree.value, -1);print(tree.right, tree.value, 1);}}public void print() {if (root != null) {print(root, root.value, 0);}}}

//测试public class Main {public static void main(String[] args) {RBTree<Integer> rbTree = new RBTree<>();rbTree.insert(10);rbTree.insert(40);rbTree.insert(30);rbTree.insert(60);rbTree.insert(90);rbTree.insert(70);rbTree.insert(20);rbTree.insert(50);rbTree.insert(80);System.out.printf("== 前序遍历: ");rbTree.preOrder();System.out.printf("\n== 中序遍历: ");rbTree.inOrder();System.out.printf("\n== 后序遍历: ");rbTree.postOrder();System.out.printf("\n");rbTree.print();}}