从二叉搜索树到AVL树再到红黑树 B树

这几种树都属于数据结构中较为复杂的，在平时面试中，经常会问理解用法，但一般不会问具体的实现，所以今天来梳理一下这几种树之间的区别与联系，感谢知乎用户@Cailiang，这篇文章参考了他的专栏。

二叉查找树

是一棵空树，或是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

插入数据：

1 如果根节点为空，则将插入的节点作为根节点

2 否则和根节点比较（我们是通过key来比较，所以 K 必须是实现了Comparable接口的对象）如果比根节点小，则新节点会插入到左子树中，如果比根节点大，则新节点会插入到右子树中，如果和根节点相等，则更新根节点的值

通过key查询：

1 如果根节点为空，返回 null

2 如果，key 和根节点的key相同，则返回根节点

3 如果，key比根节点的key小，则递归查找根节点的左节点

4 如果，key比根节点的key大，则递归查找根节点的右节点

删除节点：

1 将要删除的节点没有子节点 ----> 直接删除

2 将要删除的节点下有一个子节点 -----> 将要被删除的节点的子节点挂靠到将要被删除的节点的父节点上即可

3 将要删除的节点下有两个子节点 ----> 在将要被删除的节点的右子树中找到一个最小节点，然后用找到的最小节点与需要删除的节点替换。最后再将最小节点进行删除。（这里你可能有其它的方案，我们这里这么做的原因是一，右子树的最小节点一定没有左节点，处理起来会简单一些，二，这样可以保持树的高度不变，甚至是降低树的高度，树的高度越低意味着操作的时间复杂度越低。所以实现删除一个节点的原则是，用最小的代价实现删除的功能，并且保持树的高度不变甚至降低树的高度）

搜索二叉树的增删改查的性能都不错，但是在一些特殊情况下，搜索二叉树的性能可能由对数型变成线性，性能大大降低，比如插入的一组数据是有序的，那么二叉搜索树的结构将变成一个链表时间复杂度变为 O(N)，也就是说插入一组有序或局部有序的数据将会导致二叉搜索树不平衡，树的高度会很大，时间复杂度会趋近于 O(N)。

为了解决这个问题，引出了平衡二叉树(AVL)。

平衡二叉树，首先是一棵二叉查找树，但是它满足一点重要的特性：每一个结点的左子树和右子树的高度差最多为1。这个高度差限制就完全规避了上述的最坏情况，因此查找、插入和删除的时间复杂度都变成了O(lg n)。

AVL树虽然是一个完美平衡的二叉排序树，并且保证插入，删除，查找的时间复杂度为 lg n, 但是AVL树的应用却不广泛，原因就是维护一颗AVL树操作太复杂，成本太高。当我们对一颗AVL树进行插入或删除的操作时，我们需要不断的回朔来修改平衡因子（左子树的高度减去右字树的高度），需要通过左旋转，右旋转来保证每个节点的左右子树的高度差不超过1。这些复杂的操作甚至抵消了AVL树给我们带来的性能上的提升，所以我们一般不会使用AVL树。

红黑树

吸取了AVL树和2-3树的思想，但放弃了AVL树完美平衡的特性，改为局部平衡或完美黑色平衡；放弃了2-3树3节点，改为通过颜色（红色和黑色）来区分不同的节点类型，这样就降低了维护平衡的成本和实现的复杂度，可以直接使用二叉排序树的查询方法来查询无需任何修改。

恢复红黑属性需要少量(O(log n))的颜色变更(这在实践中是非常快速的)并且不超过三次树旋转(对于插入是两次)。插入和删除为 O(log n) 次，但是这导致了非常复杂的操作。

红黑树的性质：

1 所有节点都是红色或者黑色

2 根节点为黑色

3 所有的 NULL 叶子节点都是黑色

4 如果该节点是红色的，那么该节点的子节点一定都是黑色

5 所有的 NULL 节点到根节点的路径上的黑色节点数量一定是相同的

B-Tree

前面介绍了AVL树，红黑树，它们都属于二叉树，即每个节点最多只能拥有2个子节点，而B-tree（B树）的每个节点可以拥有2个以上的子节点，所以简单概括一下：B-tree就是一颗多路平衡查找树，它广泛应用于数据库索引和文件系统中。

首先我们介绍下 m 阶B-tree的特性，那么这个 m 阶是怎么定义的呢？这里我们以一个节点能拥有的最大子节点数来表示这颗树的阶数。举个例子，如果一个节点最多有 n 个key，那么这个节点最多就会有 n+1 个子节点，这棵树就叫做 n+1（m=n+1）阶树。一颗 m 阶B-tree包括以下5条特性：

1 每个节点最多有 m 个子节点

2 除根节点和叶子节点，其它每个节点至少有 [m/2] （向上取整的意思）个子节点

3 若根节点不是叶子节点，则其至少有2个子节点

4 所有NULL节点到根节点的高度都一样

5 除根节点外，其它节点都包含 n 个key，其中 [m/2] -1 <= n <= m-1

B+ Tree是B Tree的一个变种，不同之处在于：

第一：在 B-Tree中一个含有n个子树的节点有n-1个关键字(key)。而在 B+Tree中一个含有n个子树的节点有n个关键字(key)。

为什么在拥有同样子树的情况下B+Tree的节点多需要一个key呢？那是因为 B+Tree的节点会存储该节点的子树中最小的key。

第二：B-Tree的每个节点都包含了关键字(key)以及指向包含这些关键字记录的指针。而 B+Tree非叶子节点仅用来索引，数据都保存在叶子节点中。

在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。而且这些叶子节点构成一个有序链表，即每个叶子节点会有一个指针指向其兄弟节点。在非叶子节点中只存储了关键字信息。

下面这张图画的非常好：

在数据库索引的实现中，大部分采用的是B+Tree而不是B-Tree，这又是为什么呢？

原因有二，其一是由于B+Tree 在非叶子节点中只存储了关键字信息，而没有存储指向包含这些关键字记录的指针，所以在树的高度相同时，B+Tree往往能比B-Tree存储更多的关键字信息。更最要的原因是因为 B+Tree在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。而且这些叶子节点构成一个有序链表，这样B+Tree在实现范围查询的时候就比较容易，只需要遍历这个有序链表就行。而B-tree要实现范围查询则比较困难，但范围查询又是数据库中比较常用的功能，所以数据库中大部分采用的是B+Tree而不是B-Tree。当然B-Tree也有强于B+tree的地方，例如在随机查询中，由于B-Tree的每个节点都包含了关键字(key)以及指向包含这些关键字记录的指针，所以B-Tree可能中途就查询到需要的数据，不需要遍历到叶子节点。而B+Tree由于只在叶子节点中存储了所有的关键字信息，以及指向包含这些关键字记录的指针。在非叶子节点中只存储了关键字信息，没有存储指向包含这些关键字记录的指针，所以B+Tree一定要遍历到叶子节点才能获取到包含这些关键字记录的指针。所以B-Tree的随机查询性能会高于B+Tree。

在B+树的基础上又演变出B*树，B*Tree在非叶子结点中也增加了指向兄弟节点的指针，并且它将非叶子节点上存储的关键字个数的最小值提高到 (2/3) * m，这样的话就提高了空间利用率。

  1 public class BinarySerachTree<K extends Comparable<K>, V> {
  2 
  3     private class Node {
  4         private K key; // 存储的key
  5         private V value; // 存储的值
  6         private Node leftNode; // 左节点
  7         private Node rightNode; // 右节点
  8 
  9         public Node(K key, V value, Node leftNode, Node rightNode) {
 10             super();
 11             this.key = key;
 12             this.value = value;
 13             this.leftNode = leftNode;
 14             this.rightNode = rightNode;
 15         }
 16 
 17         @Override
 18         public String toString() {
 19             return "{"key":" + this.key + ", "value":" + """ + this.value + """ + ", "leftNode":"
 20                     + this.leftNode + ", "rightNode":" + this.rightNode + "}";
 21         }
 22     }
 23 
 24     private Node root; // 根节点
 25 
 26     public void put(K key, V value) {
 27         Node newNode = new Node(key, value, null, null);
 28         if (null == root) {
 29             root = newNode;
 30         } else {
 31             upsert(null, root, newNode);
 32         }
 33     }
 34 
 35     private void upsert(Node parent, Node current, Node newNode) {
 36         if (null == current) {
 37             if (newNode.key.compareTo(parent.key) > 0) {
 38                 parent.rightNode = newNode;
 39             } else {
 40                 parent.leftNode = newNode;
 41             }
 42         } else {
 43             int result = newNode.key.compareTo(current.key);
 44             if (result == 0) {
 45                 current.value = newNode.value;
 46             }
 47             parent = current;
 48             if (result > 0) {
 49                 upsert(parent, parent.rightNode, newNode);
 50             }
 51             if (result < 0) {
 52                 upsert(parent, parent.leftNode, newNode);
 53             }
 54         }
 55     }
 56 
 57     public Node get(K key) {
 58         if (null != key) {
 59             return find(key, root); // 从根节点开始找
 60         }
 61         return null;
 62     }
 63 
 64     private Node find(K key, Node root) {
 65         if (null != root) {
 66             int result = key.compareTo(root.key);
 67             if (result == 0) {
 68                 return root;
 69             }
 70             if (result > 0) {
 71                 return find(key, root.rightNode);
 72             }
 73             if (result < 0) {
 74                 return find(key, root.leftNode);
 75             }
 76         }
 77         return null;
 78     }
 79 
 80     public boolean delete(K key) {
 81         if (null != key) {
 82             if (null != root) {
 83                 return deleteNode(key, root, null);
 84             }
 85         }
 86         return false;
 87     }
 88 
 89     private boolean deleteNode(K key, Node current, Node parent) {
 90         if (null != current) {
 91             if (key.compareTo(current.key) > 0) {
 92                 return deleteNode(key, current.rightNode, current);
 93             }
 94             if (key.compareTo(current.key) < 0) {
 95                 return deleteNode(key, current.leftNode, current);
 96             }
 97             if (key.compareTo(current.key) == 0) {
 98                 if ((null != current.leftNode) && (null != current.rightNode)) { // 将要删除的节点下有两个子节点
 99                     dleTwoChildrenNode(current);
100                     return true;
101                 } else {
102                     if ((null == current.leftNode) && (null == current.rightNode)) { // 将要删除的节点没有子节点
103                         if (current.key.compareTo(parent.key) > 0) {
104                             parent.rightNode = null;
105                         } else {
106                             parent.leftNode = null;
107                         }
108                         return true;
109                     } else { // 将要被删除的节点的子节点挂靠到将要被删除的节点的父节点上即可
110                         Node childNode = (null == current.leftNode) ? current.rightNode : current.leftNode;
111                         if (current.key.compareTo(parent.key) > 0) {
112                             parent.rightNode = childNode;
113                         } else {
114                             parent.leftNode = childNode;
115                         }
116                         return true;
117                     }
118                 }
119             }
120         }
121         return false;
122     }
123 
124     /**
125      * 处理被删除节点有两个子节点的情况
126      * @param parent
127      * 将要被删除的节点
128      */
129     private void dleTwoChildrenNode(Node parent) {
130         Node parentRight = parent.rightNode;
131         Node tmp = parentRight.leftNode;
132         if (null == tmp) {
133             parent.value = parentRight.value;
134             parent.key = parentRight.key;
135             parent.rightNode = parentRight.rightNode;
136         } else {
137             Node tmpParent = parentRight;
138             while (null != tmp.leftNode) {
139                 tmpParent = tmp;
140                 tmp = tmp.leftNode;
141             }
142             parent.value = tmp.value;
143             parent.key = tmp.key;
144             tmpParent.leftNode = tmp.rightNode;
145         }
146     }
147 
148     public static void main(String[] args) {
149 
150         BinarySerachTree<Integer, String> bst = new BinarySerachTree<Integer, String>();
151 
152         bst.put(100, "v100");
153         bst.put(50, "v50");
154         bst.put(150, "v150");
155         bst.put(20, "v20");
156         bst.put(85, "v85");
157         bst.put(10, "v10");
158         bst.put(15, "a15");
159         bst.put(75, "v75");
160         bst.put(95, "v95");
161         bst.put(65, "v65");
162         bst.put(76, "v76");
163         bst.put(60, "v60");
164         bst.put(66, "v66");
165         bst.put(61, "v61");
166 
167         System.out.println(bst.get(100));// 打印根节点
168     }
169 }

BinarySerachTree

  1 public class RedBlackTree<K extends Comparable<K>, V> {
  2 
  3     private static final byte RED = 1;
  4     private static final byte BLACK = 0;
  5 
  6     private class Node {
  7         private byte color;
  8         private K key; // 存储的key
  9         private V value; // 存储的值
 10         private Node leftNode; // 左节点
 11         private Node rightNode; // 右节点
 12         private Node parentNode; // 父节点
 13 
 14         public Node(K key, V value, Node leftNode, Node rightNode, byte color, Node parentNode) {
 15             super();
 16             this.key = key;
 17             this.value = value;
 18             this.leftNode = leftNode;
 19             this.rightNode = rightNode;
 20             this.color = color;
 21             this.parentNode = parentNode;
 22         }
 23 
 24         @Override
 25         public String toString() {
 26             return "{" + ""key":" + this.key + ", " + ""value":" + """ + this.value + """ + ", " + ""color":"
 27                     + this.color + ", " + ""leftNode":" + this.leftNode + "," + ""rightNode":" + this.rightNode
 28                     + "}";
 29         }
 30     }
 31 
 32     private Node root; // 根节点
 33 
 34     public Node getRoot() {
 35         return this.root;
 36     }
 37 
 38     private void leftRotation(Node h) {
 39         Node m = h.rightNode;
 40         // 1. 将 k 节点设置为 h 的右节点
 41         h.rightNode = m.leftNode;
 42         if (null != m.leftNode) {
 43             m.leftNode.parentNode = h;
 44         }
 45         // 2. 将 h 的父节点 赋给 m 的父节点，之后分 3 种情况讨论
 46         m.parentNode = h.parentNode;
 47         if (null == m.parentNode) { // I: 说明 h 原来是根节点，现在将 m 设置为新的根节点
 48             root = m;
 49         } else {
 50             if (h.key.compareTo(h.parentNode.key) < 0) { // II: 说明 h 原来是它父节点的左孩子，现在将 m 设置为新的左孩子
 51                 h.parentNode.leftNode = m;
 52             } else {
 53                 h.parentNode.rightNode = m; // III: 说明 h 原来是它父节点的右孩子，现在将 m 设置为新的右孩子
 54             }
 55         }
 56         // 3. 将 h 挂靠在 m 的左孩子上
 57         m.leftNode = h;
 58         h.parentNode = m;
 59     }
 60 
 61     private void rightRotation(Node m) {
 62         Node h = m.leftNode;
 63         // 1. 将 k 设置为 m 的左节点
 64         m.leftNode = h.rightNode;
 65         if (null != h.rightNode) {
 66             h.rightNode.parentNode = m;
 67         }
 68         // 2. 将 m 的父节点 赋给 h 的父节点，之后分 3 种情况讨论
 69         h.parentNode = m.parentNode;
 70         if (null == m.parentNode) { // I: 说明 m 原来是根节点，现在将 h 设置为新的根节点
 71             root = h;
 72         } else {
 73             if (m.key.compareTo(m.parentNode.key) < 0) { // II: 说明 m 原来是它父节点的左孩子，现在将 h 设置为新的左孩子
 74                 m.parentNode.leftNode = h;
 75             } else {
 76                 m.parentNode.rightNode = h; // III: 说明 m 原来是它父节点的右孩子，现在将 h 设置为新的右孩子
 77             }
 78         }
 79         // 3. 将 m 挂靠在 h 的右孩子上
 80         h.rightNode = m;
 81         m.parentNode = h;
 82     }
 83 
 84     /**
 85      * 插入新的节点，如果指定的key已经存在，则更新原来的值
 86      * 
 87      * @param key
 88      * @param value
 89      */
 90     public void put(K key, V value) {
 91         Node newNode = new Node(key, value, null, null, RED, null);
 92         if (null == root) {
 93             root = newNode;
 94             root.color = BLACK;
 95         } else {
 96             upsert(null, root, newNode);
 97         }
 98     }
 99 
100     private void upsert(Node parent, Node current, Node newNode) {
101         if (null == current) {
102             if (newNode.key.compareTo(parent.key) > 0) {
103                 parent.rightNode = newNode;
104             } else {
105                 parent.leftNode = newNode;
106             }
107             newNode.parentNode = parent;
108             upsertFix(newNode); // 插入新节点后 对红黑树进行修复
109         } else {
110             int result = newNode.key.compareTo(current.key);
111             if (result == 0) {
112                 current.value = newNode.value;
113             }
114             parent = current;
115             if (result > 0) {
116                 upsert(parent, parent.rightNode, newNode);
117             }
118             if (result < 0) {
119                 upsert(parent, parent.leftNode, newNode);
120             }
121         }
122     }
123 
124     private void upsertFix(Node newNode) {
125         Node parent = newNode.parentNode;
126         if (RED == parent.color) { // 父节点如果是黑节点 则不需要处理
127             Node grandfather = parent.parentNode;
128             if (parent == grandfather.leftNode) { // 1. 父节点原来是 左节点
129                 Node uncle = grandfather.rightNode;
130                 if ((null != uncle) && (RED == uncle.color)) { // case 3: 叔叔节点是红色
131                     uncleRedFix(newNode);
132                 } else { // 叔叔节点为 NULL 或者 是黑色节点
133                     if (newNode.key.compareTo(parent.key) < 0) { // case 1: 叔叔节点是黑色，插入到左子树中
134                         leftNodeFix(grandfather, parent);
135                     } else { // case 2: 叔叔节点是黑色，插入到右子树中
136                         leftRotation(parent);
137                         leftNodeFix(grandfather, newNode); // 我们将 parent 节点作为“新插入的节点”，这样 真正新插入的节点 newNode 就是父节点
138                     }
139                 }
140             } else { // 1. 父节点原来是 右节点
141                 Node uncle = grandfather.leftNode;
142                 if ((null != uncle) && (RED == uncle.color)) { // case 3: 叔叔节点是红色
143                     uncleRedFix(newNode);
144                 } else { // 叔叔节点为 NULL 或者 是黑色节点
145                     if (newNode.key.compareTo(parent.key) > 0) { // case 1: 叔叔节点是黑色，插入到右子树中
146                         rightNodeFix(grandfather, parent);
147                     } else { // case 2: 叔叔节点是黑色，插入到左子树中
148                         rightRotation(parent);
149                         rightNodeFix(grandfather, newNode); // 我们将 parent 节点作为“新插入的节点”，这样 真正新插入的节点 newNode 就是父节点
150                     }
151                 }
152             }
153         }
154     }
155 
156     /**
157      * 处理 父节点原来是 左节点 的 case 1 的情况: 叔叔节点是黑色，插入到左子树中
158      * 
159      * @param grandfather
160      * @param parent
161      */
162     private void leftNodeFix(Node grandfather, Node parent) {
163         parent.color = BLACK;
164         grandfather.color = RED;
165         rightRotation(grandfather);
166     }
167 
168     /**
169      * 处理 父节点原来是 右节点 的 case 1 的情况: 叔叔节点是黑色，插入到右子树中
170      * 
171      * @param grandfather
172      * @param parent
173      */
174     private void rightNodeFix(Node grandfather, Node parent) {
175         parent.color = BLACK;
176         grandfather.color = RED;
177         leftRotation(grandfather);
178     }
179 
180     /**
181      * 处理 case 3: 叔叔节点是红色
182      * 
183      * @param newNode
184      */
185     private void uncleRedFix(Node newNode) {
186         Node parent = newNode.parentNode;
187         if ((null != parent) && (RED == parent.color)) {
188             Node grandfather = parent.parentNode;
189             Node uncle = grandfather.leftNode;
190             if (parent == grandfather.leftNode) {
191                 uncle = grandfather.rightNode;
192             }
193             parent.color = BLACK;
194             uncle.color = BLACK;
195             if (root != grandfather) {
196                 grandfather.color = RED;
197                 upsertFix(grandfather);
198             }
199         }
200     }
201 
202     /**
203      * 删除 叶子节点 后的修复过程
204      * 
205      * @param deletedNode
206      *            被删除的节点
207      * @param deletedNodeParent
208      *            被删除节点的父节点
209      */
210     private void deleteLeafFix(Node deletedNode) {
211         while ((deletedNode != root) && (BLACK == deletedNode.color)) {
212             Node parent = deletedNode.parentNode;
213             Node brother = getBrother(deletedNode);
214             if (deletedNode.key.compareTo(parent.key) > 0) { // 删除的是右叶子节点
215                 if (RED == brother.color) { // case5: 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
216                     brother.color = BLACK;
217                     brother.rightNode.color = RED;
218                     rightRotation(parent);
219                     break;
220                 } else {
221                     if ((null == brother.leftNode) && (null == brother.rightNode)) { // case4: 兄弟节点是黑色的，且没有子节点
222                         brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
223                         deletedNode = parent;
224                     } else {
225                         if ((null != brother.leftNode) && (RED == brother.leftNode.color)) {// case1:
226                                                                                             // 兄弟节点是黑色的，且有一个左节点（可以断定
227                                                                                             // 左节点是红色的）
228                             // case3: 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
229                             brother.color = parent.color;
230                             parent.color = BLACK;
231                             brother.leftNode.color = BLACK;
232                             rightRotation(parent);
233                             break;
234                         } else {// case2: 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
235                             brother.rightNode.color = BLACK;
236                             brother.color = RED;
237                             leftRotation(brother);
238                         }
239                     }
240                 }
241             } else {// 删除的是左叶子节点
242                 if (RED == brother.color) { // case5 : 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
243                     brother.color = BLACK;
244                     brother.leftNode.color = RED;
245                     leftRotation(parent);
246                     break;
247                 } else {
248                     if ((null == brother.leftNode) && (null == brother.rightNode)) { // case4: 兄弟节点是黑色的，且没有子节点
249                         brother.color = RED; // 将兄弟节点设为红色，将父节点设为当前节点递归， 直到根节点，或遇到红色节点，
250                         deletedNode = parent;
251                     } else {
252                         if ((null != brother.rightNode) && (RED == brother.rightNode.color)) { // case1 :
253                                                                                                 // 兄弟节点是黑色的，且有一个右节点（可以断定
254                                                                                                 // 右节点是红色的）
255                             // case3 : 兄弟节点是黑色的，且有两个节点（可以断定 左右节点都是红色的） 这个和情况 1 是一样的
256                             brother.color = parent.color;
257                             parent.color = BLACK;
258                             brother.rightNode.color = BLACK;
259                             leftRotation(parent);
260                             break;
261                         } else { // case2: 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的）
262                             brother.leftNode.color = BLACK;
263                             brother.color = RED;
264                             rightRotation(brother);
265                         }
266                     }
267                 }
268             }
269         }
270 
271         deletedNode.color = BLACK;
272     }
273 
274     private Node getBrother(Node node) {
275         if (null == node) {
276             return null;
277         }
278         Node parent = node.parentNode;
279         if (null == parent) {
280             return null;
281         }
282         if (node.key.compareTo(parent.key) > 0) {
283             return parent.leftNode;
284         } else {
285             return parent.rightNode;
286         }
287     }
288 
289     public boolean delete(K key) {
290         if (null != key) {
291             if (null != root) {
292                 return deleteNode(key, root, null);
293             }
294         }
295         return false;
296     }
297 
298     private boolean deleteNode(K key, Node current, Node parent) {
299         if (null != current) {
300             if (key.compareTo(current.key) > 0) {
301                 return deleteNode(key, current.rightNode, current);
302             }
303             if (key.compareTo(current.key) < 0) {
304                 return deleteNode(key, current.leftNode, current);
305             }
306             if (key.compareTo(current.key) == 0) {
307                 if ((null != current.leftNode) && (null != current.rightNode)) { // 将要删除的节点下有两个子节点
308                     dleTwoChildrenNode(current);
309                     return true;
310                 } else {
311                     if ((null == current.leftNode) && (null == current.rightNode)) { // 将要删除的节点没有子节点
312                         deleteLeafFix(current);
313                         if (current.key.compareTo(parent.key) > 0) {
314                             parent.rightNode = null;
315                         } else {
316                             parent.leftNode = null;
317                         }
318                         return true;
319                     } else { // 将要删除的节点下有一个子节点,
320                         dleOneChildNode(current);
321                         return true;
322                     }
323                 }
324             }
325         }
326         return false;
327     }
328 
329     private void dleOneChildNode(Node delNode) {
330         Node replaceNode = (null == delNode.leftNode) ? delNode.rightNode : delNode.leftNode;
331         deltetLeafNode(delNode, replaceNode);
332     }
333 
334     /**
335      * 处理被删除节点有两个子节点的情况
336      * 
337      * @param target
338      *            将要被删除的节点
339      */
340     private void dleTwoChildrenNode(Node target) {
341         Node replaceNode = successor(target);
342         if ((null == replaceNode.rightNode) && (null == replaceNode.leftNode)) {
343             deltetLeafNode(target, replaceNode);
344         } else {
345             target.key = replaceNode.key;
346             target.value = replaceNode.value;
347             dleOneChildNode(replaceNode);
348         }
349     }
350 
351     private void deltetLeafNode(Node target, Node replaceNode) {
352         target.key = replaceNode.key;
353         target.value = replaceNode.value;
354         deleteLeafFix(replaceNode);
355         if (replaceNode == replaceNode.parentNode.rightNode) {
356             replaceNode.parentNode.rightNode = null;
357         } else {
358             replaceNode.parentNode.leftNode = null;
359         }
360     }
361 
362     // 找后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"
363     private Node successor(Node node) {
364         if (node == null) {
365             return null;
366         }
367         if (null != node.rightNode) { // 获取 后继节点
368             Node p = node.rightNode;
369             while (null != p.leftNode) {
370                 p = p.leftNode;
371             }
372             return p;
373         } else {
374             Node p = node.parentNode;
375             Node ch = node;
376             while (p != null && ch == p.rightNode) {
377                 ch = p;
378                 p = p.parentNode;
379             }
380             return p;
381         }
382     }
383 
384     public static void main(String[] args) {
385 
386         RedBlackTree<Integer, String> bst = new RedBlackTree<Integer, String>();
387 
388         bst.put(100, "v100");
389         bst.put(50, "v50");
390         bst.put(150, "v150");
391         bst.put(20, "v20");
392         bst.put(85, "v85");
393         bst.put(10, "v10");
394         bst.put(15, "a15");
395         bst.put(75, "v75");
396         bst.put(95, "v95");
397         bst.put(65, "v65");
398         bst.put(76, "v76");
399         bst.put(60, "v60");
400         bst.put(66, "v66");
401         bst.put(61, "v61");
402 
403         // 当前节点是左节点 的 5中情况
404         // bst.delete(15); // 1. 兄弟节点是黑色的，且有一个右节点（可以断定 右节点是红色的）
405 
406         // 2. 兄弟节点是黑色的，且有一个左节点（可以断定 左节点是红色的
407         // bst.put(140, "v140");
408         // bst.delete(95);
409 
410         // 4. 兄弟节点是黑色的，且没有子节点
411         // bst.delete(66);
412 
413         // 5. 如果该兄弟节点是红色的，那么根据红黑树的特性可以得出它的一定有两个黑色的子节点
414         // bst.delete(95);
415         // bst.delete(15);
416 
417         System.out.println(bst.getRoot());
418     }
419 }

RedBlackTree