数据结构学习（十三）：红黑树（RBTree）

一、基本概念

（一）红黑树的五个性质：

1. 所有的节点要么是黑色的要么是红色的；
2. 根节点是黑色的；
3. 叶子结点是黑色的；
4. 每一个红色节点的子节点都是黑色的；
5. 从任意节点到子节点经过的黑色节点个数是相同的。

为了解释以上五个性质，我们先来了解一下23树这种数据结构，红黑树的基本设计思想和23树有着异曲同工之妙。

---

（二）23树

1.步骤演示：

->由图可见，插入的新节点会和原始节点先融合在一起，达到一定数量时他们会分开

->这保证了无论什么情况，23树都能够保持绝对的平衡

我们继续添加元素，看看如果不止3个元素会发生什么？

 

->由此可见，继续添加元素时，4向上和6进行融合，形成一个带三个孩子节点的融合父亲节点（4,6）

（三）红黑树

 现在我们来看看红黑树和23树之间有什么异同点：

->从整体上，二者都保持了绝对的平衡

->从具体上，红色节点所在位置表示存在融合节点，它和它的父亲节点构成了一个融合的节点

如：（6,12）（17,33）（66,88）

（四）解释红黑树的性质：

1.红黑树的节点要么是红色要么是黑色

->基本定义

2.红黑树的根节点是黑色的

->因为红色节点表示它和它的父亲节点组成了一个融合节点，而根节点没有父亲节点，因此根节点只能是黑色的，不能是红色的。

->如果这棵树为空的话，root==null，此时根节点也为黑色的。

3.红黑树的叶子结点是黑色的

->这里的叶子结点特指null节点，也就是将null当成叶子节点

->这点性质与性质2中root==null时根节点为黑色相吻合。

4.红色节点的孩子节点必为黑色

->这个性质我们可以通过23树的示意图来理解，如果一个节点是融合节点，那么他的孩子节点要么是单独节点，要么也是融合节点。

->在红黑树中，融合节点的红色节点是孩子，黑色节点是父亲。

->分类讨论：

（1）如果融合节点（17,33）的孩子节点是单独节点（18）：那么红色（17）节点的孩子节点是黑色（18）的；

（2）如果融合节点（17,22）的孩子及诶单是融合节点（6,12）：那么红色（17）节点的孩子也是黑色（12）的。

/************************************综上所述：红色节点的孩子节点是黑色的*******************************************/

5.从任意黑色节点到叶子节点经过的路径长度总是相等的

->通过23树我们可以看出，任意节点到叶子节点的高度都是固定的

例如：42~12=3 42~18=3......

->由于融合节点和单节点都只包含一个黑色节点，因此红黑树中从任意黑色节点到叶子节点经过的路径长度就等于高度大小，高度总是相等，经过的黑色节点数量也总是相等的。

二、代码实现

1.辅助函数：在之后的构造过程中会调用到

最开始的时候根节点都是黑色的，随后添加的一个节点，这个节点总是红色的，意味着需要向上融合。

继续添加节点：

（1）：相当于23树种的暂存态（3节点状态），将其进行颜色反转，使得根节点继续向上融合。

（2）：先进行右旋转，将其转换成（1）中的状态，然后再进行颜色反转

（3）：新进行右旋转，将其转换成（2）中的状态，随后重复（2）中的操作

 // 判断节点node的颜色private boolean isRed(Node node){if(node == null)return BLACK;return node.color;}//   node                     x//  /   \     左旋转         /  \// T1   x   --------->   node   T3//     / \              /   \//    T2 T3            T1   T2private Node leftRotate(Node node){Node x = node.right;// 左旋转node.right = x.left;x.left = node;x.color = node.color;node.color = RED;return x;}//     node                   x//    /   \     右旋转       /  \//   x    T2   ------->   y   node//  / \                       /  \// y  T1                     T1  T2private Node rightRotate(Node node){Node x = node.left;// 右旋转node.left = x.right;x.right = node;x.color = node.color;node.color = RED;return x;}// 颜色翻转private void flipColors(Node node){node.color = RED;node.left.color = BLACK;node.right.color = BLACK;}

2.构造函数和简单方法：

public class RBTree<K extends Comparable<K>, V> {private static final boolean RED = true;private static final boolean BLACK = false;private class Node{public K key;public V value;public Node left, right;public boolean color;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;color = RED;}}private Node root;private int size;public RBTree(){root = null;size = 0;}public int getSize(){return size;}public boolean isEmpty(){return size == 0;}// 判断节点node的颜色private boolean isRed(Node node){if(node == null)return BLACK;return node.color;}// 返回以node为根节点的二分搜索树中，key所在的节点private Node getNode(Node node, K key){if(node == null)return null;if(key.equals(node.key))return node;else if(key.compareTo(node.key) < 0)return getNode(node.left, key);else // if(key.compareTo(node.key) > 0)return getNode(node.right, key);}public boolean contains(K key){return getNode(root, key) != null;}public V get(K key){Node node = getNode(root, key);return node == null ? null : node.value;}public void set(K key, V newValue){Node node = getNode(root, key);if(node == null)throw new IllegalArgumentException(key + " doesn't exist!");node.value = newValue;}// 返回以node为根的二分搜索树的最小值所在的节点private Node minimum(Node node){if(node.left == null)return node;return minimum(node.left);}// 删除掉以node为根的二分搜索树中的最小节点// 返回删除节点后新的二分搜索树的根private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}}

3.重点函数（增删以及如何维护平衡性质）

 （1）添加：

 // 向红黑树中添加新的元素(key, value)public void add(K key, V value){root = add(root, key, value);root.color = BLACK; // 最终根节点为黑色节点}// 向以node为根的红黑树中插入元素(key, value)，递归算法// 返回插入新节点后红黑树的根private Node add(Node node, K key, V value){if(node == null){size ++;return new Node(key, value); // 默认插入红色节点}if(key.compareTo(node.key) < 0)node.left = add(node.left, key, value);else if(key.compareTo(node.key) > 0)node.right = add(node.right, key, value);else // key.compareTo(node.key) == 0node.value = value;if (isRed(node.right) && !isRed(node.left))node = leftRotate(node);if (isRed(node.left) && isRed(node.left.left))node = rightRotate(node);if (isRed(node.left) && isRed(node.right))flipColors(node);return node;}

（2）删除

 // 从二分搜索树中删除键为key的节点public V remove(K key){Node node = getNode(root, key);if(node != null){root = remove(root, key);return node.value;}return null;}private Node remove(Node node, K key){if( node == null )return null;if( key.compareTo(node.key) < 0 ){node.left = remove(node.left , key);return node;}else if(key.compareTo(node.key) > 0 ){node.right = remove(node.right, key);return node;}else{   // key.compareTo(node.key) == 0// 待删除节点左子树为空的情况if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 待删除节点右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 待删除节点左右子树均不为空的情况// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点// 用这个节点顶替待删除节点的位置Node successor = minimum(node.right);successor.right = removeMin(node.right);successor.left = node.left;node.left = node.right = null;return successor;}}

注：文中图片引用慕课liuyubobobo老师的课程讲解，主要目的是为了总结自己的学习历程，分享心得体会，如有转发请标注此项。