转载

红黑树-想说爱你不容易

前言：

记得在大一懵懵懂懂的时候就接触了红黑树的算法。但由于当时内功尚浅，无法将其内化，只是觉得它很神奇，是个好算法，设计它的人很牛！现今重拾起这个算法，不得不再次被它的精妙所折服！编写本文，是希望以鄙人的理解将红黑树算法的精髓向博客园的园友陈述一番，也希望对其有独特见解的朋友能不吝赐教。准备好了的话，我们就开始吧 ~

--------------------------------------------

Part I:BST

作为开始，我们得先谈谈二叉树（ Binary Search Tree ）。

1.假设存在一个如下简单的键值字符表：

Key Value

A 2

C 1

B 6

B 11

H 1

J 3

要求你按照读入顺序建立这样一棵二叉查找树，建好之后要求能够进行对于的查询操作。

源于二分查找的思想，二叉查找树有这样一个特点：

对于树上的任意一个结点，如果它有左右子结点的话， 其结点大小必定大于其左子结点且小于其右子结点。

2.查找get(key)

由于单独建立一个二叉查找树起初不好分析，我们就假设现在有一棵已经构造好二叉查找树。我们仅需要思考如何在其上面进行查找操作。

根据二分查找的思想，我们可以按照下面步骤进行查找：

Step1: 将需要查找的 key 与二叉查找树的当前根节点的 key 作比较，得到比较结果后进行下面的 step2;

Step2: 若查找的 key 比根节点的 key 小，则递归从根节点的左子树进行同样的查找 key 操作；若比根节点的 key 大，则递归地从根节点的右子树进行同样的查找 key 操作；

若，查找的 key 刚好等于当前根节点的 key ，则返回当前 key 对应的 value ，结束！

3.插入 put(key,value)

假设现在已经有了一个二叉查找树，我们要插入一对键值（ key-value ）。源于查找过程的经验，我们知道插入操作其实近似于查找操作。因为，我们插入的时候同样是拿 key 跟当前根节点的 key 比较，之后再确定是往左走还是右走，或者是更新当前值（ key=root.key 时）。

红黑树-想说爱你不容易

Code:

 1 package com.gdufe.binarysearchtree;  2   3 import java.io.File;  4 import java.util.Scanner;  5   6 public class BST<Key extends Comparable<Key>, Value> {  7   8     Node root; // 维护根节点  9  10     class Node { // 二叉树的结点 11         Key key; 12         Value value; 13         Node left, right; 14  15         public Node(Key key, Value value) { // 初始化结点 16             this.key = key; 17             this.value = value; 18         } 19     } 20  21     public Value get(Key key) { 22         return get(root, key); 23     } 24  25     //查找操作 26     public Value get(Node x, Key key) { 27         if (x == null) 28             return null; 29         int cmp = key.compareTo(x.key); 30         if (cmp < 0) 31             return get(x.left, key); 32         else if (cmp > 0) 33             return get(x.right, key); 34         else 35             return x.value; 36     } 37  38     public void put(Key key, Value value) { 39         root = put(root, key, value); 40     } 41     //插入操作 42     public Node put(Node x, Key key, Value value) { 43         if (x == null) 44             return new Node(key, value); 45         int cmp = key.compareTo(x.key); 46         if (cmp < 0) 47             x.left = put(x.left, key, value); 48         else if (cmp > 0) 49             x.right = put(x.right, key, value); 50         else 51             x.value = value; 52         return x; 53     } 54  55     public static void main(String[] args) throws Exception { 56         Scanner input = new Scanner(new File("data_BST.txt")); 57         BST<String, Integer> bst = new BST<String, Integer>(); 58         while (input.hasNext()) { 59             String key = input.next(); 60             int value = input.nextInt(); 61             bst.put(key, value); 62         } 63         System.out.println(bst.get("H")); 64         System.out.println(bst.get("B")); 65     } 66  67 }

输出结果：

1 11

分析：

插入或查找时，有可能最坏情况树不断恶意生长（垂直生长），此时的时间复杂度为： O （ N ） , 平均的时间复杂度为： O(lgN)

----------------------------------------

Part II:RedBlackBST

1. 2-3 树

在二叉树的基础之上，我们引入了平衡 2-3 树。简单地说，二叉树每个结点至多只能有 2 个子结点（称为“ 2 结点”），而现在我们可以通过将 2 个结点“绑”在一起形成一个有 3 个子结点的“ 3 结点”。见下图：

红黑树-想说爱你不容易

由于查找操作较简单，我们重点讨论它的插入操作。同样基于上面所给的数据，见图：

红黑树-想说爱你不容易

------------------------------------------------

2.红黑二叉查找树（简称“红黑树”）

那么问题来了，我们该如何实现这样一棵 2-3 树呢？正常的思维当然是希望在原先的 Node 结构中进行重构，再构造一个嵌套的 BIGNode 。但巧妙的地方就在这里，我们可以以之前的二叉查找树为基础，把结点之间的链接分为“红链接”和“黑链接”。其中，红连接通过连接两个 2 结点组成 3 结点，黑连接是之前二叉查找树的普通连接。为了方便，我们不妨把 3 结点统一表示为一条左斜的红色链接。如图：

红黑树-想说爱你不容易

上面通过定义红黑树的规则实现我们等价的 2-3 树结构，于是红黑树也就有了下面等价的定义。

含有红黑链接并且满足下列条件的二叉查找树：

1) 红链接均为左链接

2) 没有任何结点同时和 2 条红链接相连

3) 任意空链接到根节点路径上的黑链接数相同

---------------------------------------------

既然从上面的阐述中，我们得出了“红黑树≈2-3 树",我们我们紧接着用上面的数据构建我们的红黑树，见图：

红黑树-想说爱你不容易

其中，存在着3个关键操作：

左旋：当结点出现左子结点为黑，右子结点为红时，进行左旋转；

右旋：当结点出现左子结点以及左子结点的左结点均为红时，进行右旋转；

变色：当结点出现左右子结点均为红时，进行变色操作（2个子链接均变黑色，并将红链接向上传递！）

具体，见下图：红黑树-想说爱你不容易

Code:

  1 package com.gdufe.binarysearchtree;   2    3 import java.io.File;   4 import java.util.Scanner;   5    6 public class RedBlackTree<Key extends Comparable<Key>, Value> {   7    8     Node root; // 维护根节点   9   10     final static boolean RED = true;  11     final static boolean BLACK = false;  12   13     class Node { // 二叉树的结点  14         Key key;  15         Value value;  16         boolean color;  17         Node left, right;  18   19         public Node(Key key, Value value, boolean color) { // 初始化结点  20             this.key = key;  21             this.value = value;  22             this.color = color;  23         }  24     }  25   26     public Value get(Key key) {  27         return get(root, key);  28     }  29   30     // 右旋  31     public Node rotateRight(Node h) {  32         Node x = h.left;  33         h.left = x.right;  34         x.right = h;  35         x.color = h.color;  36         h.color = RED;  37         return x;  38     }  39   40     // 左旋  41     public Node rotateLeft(Node h) {  42         Node x = h.right;  43         h.right = x.left;  44         x.left = h;  45         x.color = h.color;  46         h.color = RED;  47         return x;  48     }  49   50     // 变色处理  51     public void flipColors(Node h) {  52         h.left.color = BLACK;  53         h.right.color = BLACK;  54         h.color = RED;  55     }  56     public boolean isRed(Node x){  57         if(x==null) return false;  58         else return x.color;  59     }  60     public Value get(Node x, Key key) {  61         if (x == null)  62             return null;  63         int cmp = key.compareTo(x.key);  64         if (cmp < 0)  65             return get(x.left, key);  66         else if (cmp > 0)  67             return get(x.right, key);  68         else  69             return x.value;  70     }  71   72     public void put(Key key, Value value) {  73         root = put(root, key, value);  74         root.color = BLACK;  75     }  76   77     public Node put(Node x, Key key, Value value) {  78         if (x == null)  79             return new Node(key, value, RED); // 添加的结点链接为红色  80         int cmp = key.compareTo(x.key);  81         if (cmp < 0)  82             x.left = put(x.left, key, value);  83         else if (cmp > 0)  84             x.right = put(x.right, key, value);  85         else {  86             x.value = value;  87         }  88         // 判断是否需要左旋，右旋，变色操作  89         if (x != null) {  90             if (!isRed(x.left) && isRed(x.right))  91                 x = rotateLeft(x);   92             if (isRed(x.left) && isRed(x.left.left))  93                 x = rotateRight(x);  94             if (isRed(x.left ) && isRed(x.right))  95                 flipColors(x);  96         }  97   98         return x;  99     } 100  101     public static void main(String[] args) throws Exception { 102         Scanner input = new Scanner(new File("data_BST.txt")); 103         RedBlackTree<String, Integer> bst = new RedBlackTree<String, Integer>(); 104         while (input.hasNext()) { 105             String key = input.next(); 106             int value = input.nextInt(); 107             bst.put(key, value); 108         } 109         System.out.println(bst.get("H")); 110         System.out.println(bst.get("B")); 111     } 112  113 }