红黑树原理解析

为什么会有红黑树红黑树的4条性质红黑树的变换例子加以讲解最后贴上整构建过程实现代码

为什么会有红黑树

叉搜索树对于某个节点而言，其左子树的节点关键值都小于该节点关键值，右子树的所有节点关键值都大于该节点关键值。

二叉搜索树作为一种数据结构，其查找、插入和删除操作的时间复杂度都为O(logn),底数为2。但是我们说这个时间复杂度是在平衡的二叉搜索树上体现的，也就是如果插入的数据是随机的，则效率很高，

但是如果插入的数据是有序的，比如从小到大的顺序【10,20,30,40,50】插入到二叉搜索树中： 从大到小就是全部在左边，这和链表没有任何区别了，这种情况下查找的时间复杂度为O(N)，而不是O(logN)。当然这是在最不平衡的条件下，实际情况下，二叉搜索树的效率应该在O(N)和O(logN)之间，这取决于树的不平衡程度。

那么为了能够以较快的时间O(logN)来搜索一棵树，我们需要保证树总是平衡的（或者大部分是平衡的），也就是说每个节点的左子树节点个数和右子树节点个数尽量相等。红-黑树的就是这样的一棵平衡树，对一个要插入的数据项（删除也是），插入例程要检查会不会破坏树的特征，如果破坏了，程序就会进行纠正，根据需要改变树的结构，从而保持树的平衡。

红黑树的4条性质

每个节点不是黑色就是红色根节点是黑色不能有两个红色节点相连所有叶子节点都是黑色的空节点NIL,也就是说，叶子节点不能存储数据每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点

红黑树的变换

为了满足红黑树的性质，因此出现了变色和旋转。

改变颜色，最简单，红变黑，黑变红。左旋：针对于点旋，但是点上面的子树也跟着转。右旋

先看下左旋和右旋的动图。 左旋：

以E节点为基准，向左旋转，S的左子树变为E的右子树。

右旋： 以S节点为基准，向右旋转。

那么该怎么选择以上三种方式？

例子加以讲解

插入6，新插入的节点是红色节点（规定）

当前节点是红色节点，父节点是红色节点，叔叔节点也是红色节点，所以换颜色。 父亲节点7变为黑色，叔叔节点13变为黑色，祖父节点12变为红色。

满足左旋条件

变为： 此时满足右旋的条件：

父亲节点是红色节点叔叔节点是黑色节点当前点是左子树 S为根节点19，E为12。右旋的比较麻烦点：

最后变为：

最后贴上整构建过程

* 左旋右旋动图：

实现代码

代码实现的话了解下即可，这个平时也不会写道。可看可不看，最重要的是搞懂

红黑树的四条特性？ 红黑树什么时候变换颜色？ 左旋和右旋是什么条件下触发的？

import java.util.Arrays; import java.util.Scanner; public class RedBlackTree { private final int R = 0; private final int B = 1; private class Node { int key = -1; int color = B; // 颜色 Node left = nil; // nil表示的是叶子结点 Node right = nil; Node p = nil; Node(int key) { this.key = key; } @Override public String toString() { return "Node [key=" + key + ", color=" + color + ", left=" + left.key + ", right=" + right.key + ", p=" + p.key + "]" + "\r\n"; } } private final Node nil = new Node(-1); private Node root = nil; public void printTree(Node node) { if (node == nil) { return; } printTree(node.left); System.out.print(node.toString()); printTree(node.right); } private void insert(Node node) { Node temp = root; if (root == nil) { root = node; node.color = B; node.p = nil; } else { node.color = R; while (true) { if (node.key < temp.key) { if (temp.left == nil) { temp.left = node; node.p = temp; break; } else { temp = temp.left; } } else if (node.key >= temp.key) { if (temp.right == nil) { temp.right = node; node.p = temp; break; } else { temp = temp.right; } } } fixTree(node); } } private void fixTree(Node node) { while (node.p.color == R) { Node y = nil; if (node.p == node.p.p.left) { y = node.p.p.right; if (y != nil && y.color == R) { node.p.color = B; y.color = B; node.p.p.color = R; node = node.p.p; continue; } if (node == node.p.right) { node = node.p; rotateLeft(node); } node.p.color = B; node.p.p.color = R; rotateRight(node.p.p); } else { y = node.p.p.left; if (y != nil && y.color == R) { node.p.color = B; y.color = B; node.p.p.color = R; node = node.p.p; continue; } if (node == node.p.left) { node = node.p; rotateRight(node); } node.p.color = B; node.p.p.color = R; rotateLeft(node.p.p); } } root.color = B; } void rotateLeft(Node node) { if (node.p != nil) { if (node == node.p.left) { node.p.left = node.right; } else { node.p.right = node.right; } node.right.p = node.p; node.p = node.right; if (node.right.left != nil) { node.right.left.p = node; } node.right = node.right.left; node.p.left = node; } else { Node right = root.right; root.right = right.left; right.left.p = root; root.p = right; right.left = root; right.p = nil; root = right; } } void rotateRight(Node node) { if (node.p != nil) { if (node == node.p.left) { node.p.left = node.left; } else { node.p.right = node.left; } node.left.p = node.p; node.p = node.left; if (node.left.right != nil) { node.left.right.p = node; } node.left = node.left.right; node.p.right = node; } else { Node left = root.left; root.left = root.left.right; left.right.p = root; root.p = left; left.right = root; left.p = nil; root = left; } } public void creatTree() { int data[]= {23,32,15,221,3}; Node node; System.out.println(Arrays.toString(data)); for(int i = 0 ; i < data.length ; i++) { node = new Node(data[i]); insert(node); } printTree(root); } /** * * @param args */ public static void main(String[] args) { RedBlackTree bst = new RedBlackTree(); bst.creatTree(); } }