实现

红黑查找树是2-3树的具体实现

1. 替换3-结点

  • 红黑树的基本思想:用标准的二叉查找树(全是2-结点)和一些额外信息(替换3-结点)来表示2-3查找树
  • 结点类型:(结点的颜色指的是指向该结点的链接颜色)
    • 红链接:将两个2-结点连成3-结点
    • 黑链接:2-3树中的普通链接
  1. private class Node{
  2. Key key;
  3. Value val;
  4. Node left, right;
  5. int N;
  6. //结点颜色:指向该结点链接的颜色
  7. boolean color;
  8. Node(Key key, Value val, int N, boolean color){
  9. this.key = key;
  10. this.val = val;
  11. this.N = N;
  12. this.color = color;
  13. }
  14. }

2. 等价定义

  • 红链接均为左链接
  • 没有一个结点同时和两条红链接相连(4-结点)
  • 该树是黑色平衡,即任意空链接到根结点的路径上黑链接数量相同

3. 一一对应

将红黑树中所有红链接画水平,那所有空链接到根结点的距离都将相同.再将红链接相连的结点合并,即可得到2-3树.红黑树结合了二叉树的高效查找和2-3树的平衡插入
RB1.jpg


4. 主要操作

4.1 旋转

某些操作下,可能出现红色右链接或两个连续红链接,需要旋转改变红链接指向,旋转操作保证了有序性和完美平衡性

  • 左旋:避免产生右红链接
  • 右旋:处理左侧两个连续红链接

RB2.jpg

  1. Node rotateLeft(Node h){
  2. Node x = h.right;
  3. h.right = x.left;
  4. x.left = h;
  5. x.color = h.color;//初始h的颜色不确定
  6. h.color = RED;//旋转后左链接置红色
  7. x.N = h.N;
  8. h.N = 1+size(h.left)+size(h.right);
  9. return x;
  10. }
  11. Node rotateRight(Node h){
  12. Node x = h.left;
  13. h.left = x.right;
  14. x.right = h;
  15. x.color = h.color;
  16. h.color = RED;
  17. x.N = h.N;
  18. h.N = 1+size(h.left)+size(h.right);
  19. return x;
  20. }

4.2 插入

4.2.1 向2-结点插入新键

当只有一个2-结点时,插入一个新键后立刻旋转

  • 新键<老键:增加红色结点,新树等价于3-结点
  • 新键>老键:增加红色结点,但产生红右链,root=rotateLeft(root),旋转修正

4.2.2 向双键树(3-结点)插入新键

  • 新键>原数中两个键:最简单的情况,直接连接到3-结点右链接.此时树是平衡的,将两个链接的颜色由黑变红,即得到一棵由三个结点组成的,高为2的平衡树,真好对于2-3树
  • 新键<原数中两个键:连接到最左边的空链接,形成了连续两条红链接(4-结点),只需把上层红链接右旋转即可回到情况一
  • 新键介于二者之间:连接到左结点的右链(红色),有形成两条连续红链接,将右链左旋,回到情况二

4.2.3 颜色转换

在上述向双键树插入新键操作后,子结点都由红变黑,父结点变红,这是局部变换,不会影响整棵树的黑色平衡性

  1. private void flipColors(Node h){
  2. h.color = RED;
  3. h.left.color = BLACK;
  4. h.right.color = BLACK;
  5. }

4.2.4 根结点总为黑色

红色结点说明结点是3-结点的一部分,但根结点并不满足,则每次插入后根结点都设为黑,且每当根结点由红变黑,树高加1

4.2.5 红链接向上传递

在2-3树中,在一个3-结点下插入新键->临时创建4-结点->分解,传递中间值到父结点->父结点是一个2-结点或为根结点->若为后者,则分解根结点.
对应到红黑树中就是红链接向上传递,插入->旋转->颜色转换->红链接转移至中结点->重复(和新插入结点效果一样)->直到非红右链接/非连续红链接/非根结点
RB3.jpg
4.2.6 插入算法

  • 插入操作只有以下三种:
    • 左子结点黑色,右子结点红色->左旋
    • 左子结点和左子结点的左子结点都为红色->右旋
    • 左右子结点都为红色->颜色转换
  • 红黑树平衡性的调整是自下而上的,所以在put()递归插入语句后,再用if判断以上三种情况,并且,三条语句有顺序(根据4.2.2分析)

    1. public class RedBlackBST<Key extends Comparable<Key>, Value > {
    2. private Node root;
    3. private static final boolean RED = true;
    4. private static final boolean BLACK = false;
    5. private class Node{}
    6. private boolean isRed(Node x){
    7. if (x == null) return false;
    8. return x.color == RED;
    9. }
    10. private Node rotateLeft(Node h){}
    11. private Node rotateRight(Node h){}
    12. private void flipColors(Node h){}
    13. public int size(){ return size(root);}
    14. private int size(Node h){
    15. if (h == null) return 0;
    16. else return h.N;
    17. }
    18. public void put(Key key, Value val){
    19. root = put(root,key,val);
    20. root.color = BLACK;
    21. }
    22. private Node put(Node h, Key key, Value val){
    23. if (h == null){
    24. //新建结点都用红链接
    25. return new Node(key, val, 1, RED);
    26. }
    27. int cmp = key.compareTo(h.key);
    28. if (cmp < 0) h.left = put(h.left, key, val);//小于key,进入左子树
    29. else if(cmp > 0) h.right = put(h.right, key, val);//大于key,进入右子树
    30. else h.val = val;//已存在,则更新val
    31. //处理右侧红链接
    32. if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
    33. //处理连续红链接
    34. if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
    35. //颜色转换
    36. if (isRed(h.left) && isRed(h.right)) flipColors(h);
    37. h.N = size(h.right)+size(h.left)+1;
    38. return h;
    39. }
    40. }

示例
RB4.jpg

4.3 删除

4.3.1 自顶向下的2-3-4树
2-3-4树中允许存在4-结点,它的插入算法和2-3数的删除算法类似,因此作为引导
234Tree.jpg

  • 插入: 沿着路径向下进行变换,始终保持当前结点非4-结点(这样树底才有空间插入新键),沿查找路径向上进行变换是为了将之前创建的4-结点配平
    • 向下变换:
      1. 根结点是4-结点,分解为三个2-结点,树高加一
      2. 父结点为2-结点的4-结点,将中间结点上移构成3-结点,剩下拆分为两个2-结点
      3. 父结点为3-结点的4-结点,将中间结点上移构成4-结点,剩下拆分为两个2-结点
      4. 不会构建出出现父结点和子结点同时为4-结点的情况
      5. 树底部只可能为2-/3-结点,插入扩大一个即可
    • 向上变换:即put()中的递归后rotate()处理
    • 红黑树实现2-3-4插入:
      • 4-结点由三个2-结点表示
      • 向下时分解4-结点,进行颜色转换
      • 向上时旋转配平4-结点
    • 只需要将colorFlip()语句及其if语句放在null测试和比较操作之间,就可以实现上述算法
      • 允许4-结点存在,即允许连续两个左红链接存在,所以语句提前在比较执行put()前,再下次put()时前在调整颜色(分解4-结点)—向下
      • 两个方向rotate()依旧在put()后,则在向上过程中配平4-结点—向上

4.3.2 删除最小键

  • 考虑:在树底部删除3-结点删除最小键容易实现,但若从2-结点删除一个结点,会留下一个空链接,破坏平衡性
  • 因此:删除最小键时,沿着左链接向下变换,确保当前结点非2-结点(可能是3-结点或者临时4-结点)
    1. 根结点的两种可能:
      • 根结点是2-结点且两个子结点也是2-结点:将三个结点合并为一个4-结点
      • 否则需要保证根结点的左子结点非2-结点,必要时从其右兄弟结点取一个键
    2. 沿着左链接向下时:
      • if(!isRed(h.left) && !isRed(h.left.left))
      • 若当前结点左子结点非2-结点(h.left或h.left.left中一个为红色,则h.left就在一个3-结点中),完成,继续左下深入
      • 若当前结点左子结点是2-结点而亲兄弟非2-结点,将右子结点的兄弟结点中一个键移动到左子结点中
      • 若当前结点左子结点和兄弟结点都是2-结点,将左子结点,父结点中的最小键,左子结点最近兄弟结点合并为一个4-结点,则父结点从3-变为2-或4-变为3-
    3. 最终:得到一个含有最小键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
  1. //配平4-结点函数,只有第一句话不同,其余和put最后五句一致
  2. private Node balance(Node h){
  3. if (isRed(h.right)) h = rotateLeft(h);
  4. if(!isRed(h.left) && isRed(h.right)) rotateLeft(h);
  5. if(isRed(h.left) && isRed(h.left.left)) rotateRight(h);
  6. if(isRed(h.left) && isRed(h.right)) flipColors(h);
  7. h.N = size(h.right) + size(h.left)+1;
  8. return h;
  9. }
  10. //删除时的颜色转换与插入时刚好相反
  11. private void delFlipColors(Node h){
  12. h.color = BLACK;
  13. h.left.color = RED;
  14. h.right.color = RED;
  15. }
  16. public void deleteMin(){
  17. if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
  18. root.color = RED;//为后续颜色变换准备
  19. deleteMin(root.left);
  20. if(!isEmpty()) root.color = BLACK;//根结点始终为黑色
  21. }
  22. private Node deleteMin(Node h){
  23. if (h.left == null) return null;//找到左链最底,返回null
  24. if(!isRed(h.left) && !isRed(h.left.left))//h.left是2-结点
  25. h = moveRedLeft(h);//借助兄弟结点
  26. h.left = deleteMin(h.left);
  27. return balance(h);
  28. }
  29. private Node moveRedLeft(Node h){
  30. delFlipColors(h);//Min:默认形成4-结点
  31. if (isRed(h.right.left)){//Min:当右兄弟非2-结点,借出一个键给左兄弟
  32. h.right = rotateRight(h.right);
  33. h = rotateLeft(h);
  34. }
  35. return h;
  36. }

示例
delMin.jpg


4.3.3 删除最大键

  • 删除最大键的思想和删除最小键一样
    1. 对根结点的处理:同上
    2. 沿着右链接向下时:
      • 若当前结点的左子结点非2-结点,则左旋转左子结点,成为父结点,新的右子结点一定非2-结点,为后续删除创造条件
      • if(!isRed(h.left) && !isRed(h.left.left))
      • 若当前结点右子结点非2-结点(h.right或h.right.left中一个为红色,则h.left就在一个3-结点中),完成,继续右下深入
      • 若当前结点右子结点是2-结点而左兄弟非2-结点,将右子结点,父结点中的最大键,最近左兄弟结点合并为一个4-结点
      • 若当前结点右子结点和兄弟结点都是2-结点,则将左子结点旋转,即移动一个键到右子结点
    3. 最终:得到一个含有最大键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
  1. //删除最大键
  2. public void deleteMax(){
  3. if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
  4. root.color = RED;//为后续颜色变换准备
  5. root = deleteMax(root);
  6. if (!isEmpty()) root.color = BLACK;
  7. }
  8. private Node deleteMax(Node h){
  9. if (isRed(h.left)) h = rotateRight(h);//左侧非2-结点右旋转
  10. if(h.right == null) return null;//找到右链底部,返回null
  11. if (!isRed(h.right) && !isRed(h.right.left))
  12. h = moveRedRight(h);//从左链借来键
  13. h.right = deleteMax(h.right);
  14. return balance(h);
  15. }
  16. private Node moveRedRight(Node h){
  17. //delMin与delMax这两步含义不同
  18. delFlipColors(h);//Max:默认右子结点变为非2-结点
  19. if (!isRed(h.left.left))//Max:当左兄弟是2-结点,则形成4-结点
  20. h = rotateRight(h);
  21. return h;
  22. }

示例
delMax.jpg


4.3.4 删除操作

  • 删除和delMin/delMax都要保证当前结点非2-结点,若最终找到结点在底部(左链接/右链接),则直接删除,否则就用右子树最小结点键值与其他交换,再删除右子树最小键
  1. public void delete(Key key){
  2. if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
  3. root.color = RED;//为后续颜色变换准备
  4. root = delete(root, key);
  5. if (!isEmpty()) root.color = BLACK;
  6. }
  7. private Node delete(Node h, Key key){
  8. if(key.compareTo(h.key) < 0){//cmp < 0,类比delMin
  9. if(!isRed(h.left) && !isRed(h.left.left))
  10. h = moveRedLeft(h);
  11. h.left = delete(h.left, key);
  12. }
  13. else{//cmp >= 0,类比delMax
  14. if(isRed(h.left)) h = rotateRight(h);
  15. if(key.compareTo(h.key) == 0 && (h.right == null)) return null;//找到结点,且无右子树,直接删除
  16. if(!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
  17. if(key.compareTo(h.key) == 0){//找到结点,且有后续结点,则用右子树最小结点键值替换父结点,再删去右子树最小结点
  18. h.val = get(h.right, min(h.right).key);
  19. h.key = min(h.right).key;
  20. h.right = deleteMin(h.right);
  21. }
  22. else h.right = delete(h.right, key);
  23. }
  24. return balance(h);
  25. }

示例
delete.jpg


5. 红黑树性质

5.1 性能分析

  1. 大小为N的红黑树高度不超过2lgN
    最坏情况是对应2-3树最左边路径全是3-结点而其余都为2-结点
  2. 大小为N的红黑树,根结点到任意结点的平均路径长度为~1.00lgN
  3. 红黑树中,以下操作在最坏情况下是对数级别的:
    get(),put(),min(),max(),floor(),ceiling(),rank(),select(),deleteMin(),deleteMax(),delete(),range()

红黑树是第一个可以保证**对数级别插入和查找的符号表实现**

5.2 各种符号表实现性能总结

算法 最坏查找 最坏插入 最优查找 最坏插入 支持有序操作
顺序查询(无序链表) N N N/2 N
二分查找(有序数组) lgN N lgN N/2
BST N N 1.39lgN 1.39lgN
红黑树 2lgN 2lgN 1.00lgN 1.00lgN