赞
踩
13-1 红黑树与2-3树
13-2 2-3树的绝对平衡性
13-3 红黑树与2-3树的等价性
13-4 红黑树的基本性质和复杂度分析
13-5 保持根节点为黑色和左旋转
13-6 颜色翻转和右旋转
13-7 红黑树中添加新元素
13-8 红黑树的性能测试
13-9 更多和红黑树相关的话题
13-1 红黑树与2-3树
首先,介绍一下《算法导论》中的红黑树
- 每个节点或者是红色的,或者是黑色的
- 根节点是黑色的
- 每一个叶子节点(最后的空节点)是黑色的
- 如果一个节点是红色的,那么它的孩子节点都是黑色的
- 从任意一个节点到叶子节点,经过的黑色节点是一样的
接下来我们会学习红黑树与2-3树的等价性,理解了2-3树和红黑树之间的关系,红黑树并不难!
学习2-3树,不仅对于理解红黑树有帮助,对于理解B类树,也是有巨大帮助的!
13-2 2-3树的绝对平衡性
视频介绍非常仔细,如果不记得了可以再看一遍。
(2)如果插入3-节点:本来是一个3-节点(6 12),我们插入新的元素2的话,就暂时形成了一个4-节点(2 6 12 :3个元素四个孩子),最后变形成拥有三个2-节点的子树
(3)如果插入3-节点,且此时父亲节点为2-节点: 这里我们向(2 5)节点中插入4节点
(4)如果插入3-节点,且此时父亲节点为3-节点:这里我们向(2 5)节点中插入4节点
13-3 红黑树与2-3树的等价性
将b做一个特殊标识,比如将其变成红色。b这个节点和父亲节点连接的红色边是一个特殊的边,实际上表示b和c两个节点在原来的2-3树中是一个并列的关系。并且在红黑树中,所有的红色节点都是左倾斜的(这个结论是我们定义的,不是推导出来的)
简单举个例子:
所以上一节我们说红黑树与2-3树等价是因为,任意一个2-3树都可以使用以上规则转化为一棵红黑树。
import java.util.ArrayList; 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; } // 向二分搜索树中添加新的元素(key, value) public void add(K key, V value){ root = add(root, key, value); } // 向以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) == 0 node.value = value; return node; } // 返回以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; } // 从二分搜索树中删除键为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; } }
13-4 红黑树的基本性质和复杂度分析
(1)红黑树是保持“黑平衡”的二叉树,这里的“黑平衡”是指对于从根节点开始搜索一直搜索到叶子节点,所经历的黑色节点的个数是一样的多的,是黑色的一种绝对的平衡。但严格意义上来讲,不是平衡二叉树,因为红黑树中左右子树的高度差是有可能大于1的,但红黑树的黑色节点的高度差保持着绝对的平衡,因此这就是为什么说红黑树是保持“黑平衡”的二叉树。
(2)对于红黑树来说,如果它的节点个数为n的话,相对应的它的最大高度为2logn,增删改查的操作时间复杂度均为O(logn)
(3)红黑树不会像二分搜索树一样退化成链表。
(4)对于红黑树来说添加元素和删除元素是比AVL树要快速一些,只需要查询的话AVL效率更高一些。
13-5 保持根节点为黑色和左旋转
红黑树添加新元素
2-3 树中添加一个新元素,或者添加进2-节点,形成一个3-节点;或者添加进3-节点,暂时形成一个4-节点。
在红黑树中添加新元素- - > 新的元素所在的节点永远是红色的(永远添加红色节点)
红黑树的左旋转过程:
当我们想要将42这个红色节点插入到37这个2-节点中时,我们发现根据二分搜索树添加的原则,42 > 37,因此应当将42插入到37节点的右子树,然而此时不满足红黑树左倾原则,我们此时需要进行左旋转,和AVL树相同。
简答的代码实现如下:
private Node leftRotate(Node node){
Node x = node.right;
// 左旋转
node.right = x.left;
x.left = node;
x.color = node.color;
node.color = RED;
return x;
}
这里还有一件小事:由于红黑树的实现代码量非常大,因此在面试时很少会让你写红黑树的代码。
13-6 颜色翻转和右旋转
- 而在红黑树中,三个2-节点表示的是黑色节点,每一个黑色节点它的左侧如果没有红色节点的话,它本身就代表一个单独的2-节点,所以在这种情况下,不需要旋转节点,只需要将颜色都改变为黑色即可。
- 到了这里,我们知道得到临时的4-节点后,根节点要继续向上和它的父亲节点做融合,融合意味着我们新的根节点在红黑树中要变成一个红色节点。红色的节点才表示它要和它的父亲节点去融合,至此我们便处理完这种情况。
- 经过上述一系列操作之后,我们发现原本的节点颜色正好反过来了,我们称这样的情况为颜色翻转 flipColors
接下来我们用代码实现颜色翻转的过程:
// 颜色翻转
private void flipColors(Node node){
node.color = RED;
node.left.color = BLACK;
node.right.color = BLACK;
}
(2)右旋转
这里我们将12新节点添加到(37 42)这个2-节点中,我们发现根据二分搜索树添加元素的规则,12应当添加到(37 42)的左子树中。此时在红黑树中42的左孩子和它左孩子的左孩子都是红色的节点,这样的一种形状也可以理解为一种临时的4-节点。为了得到像2-3树最后得到的子树(由三个2-节点组成的子树),首先需要对42这个节点进行一个 右旋转 的过程,然后再进行(1)颜色翻转。
接下来我们用代码实现颜色翻转的过程:
private Node rightRotate(Node node){
Node x = node.left;
// 右旋转
node.left = x.right;
x.right = node;
x.color = node.color;
node.color = RED;
return x;
}
13-7 红黑树中添加新元素
代码实现:
// 向以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) == 0 node.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; }
13-8 红黑树的性能测试
13-9 更多和红黑树相关的话题
红黑树中删除节点、左倾红黑树、右倾红黑树
红黑树统计性能更优,另一种统计性能优秀的树结构:Splay Tree (伸展树)
局部性原理:刚被访问的内容下次高概率被再次访问。
基于红黑树的Map和Set(这里,java.util中的TreeMap和TreeSet基于红黑树:))
红黑树的其他实现:算法导论中红黑树的实现
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。