一、 红黑树概述

  红黑树是对2-3树的编码,即用二叉树结点单键单值的形式来表示2-3树,具体措施是对两个结点相连的链接标记颜色。

  红链接:将相连的两个2-结点链接起来表示一个3-结点,即我们将3-结点表示为由一条左斜的红色链接相连的两个2-结点

  黑链接:即普通的2-结点

二、 红黑树特性

  红黑树是存在红黑链接并且满足如下特性的二叉树:

  1、 红链接都为左链接

  2、 没有任何一个结点同时和两条红色链接相连

  3、 红黑树是完美平衡的二叉树,即任意空链接到根结点的黑链接数量相等

  4、 红黑树的根结点链接永远是黑色

  如下为2-3树表示为红黑树的示意图

  红黑树:

   

  2-3树:

   

三、 红黑树结点的构造

  我们在二叉树结点的结构上,新增一个布尔变量color表示结点与父节点相连的链接的颜色,红链接为true,黑链接为false

/**

 * 红黑树结点

 * @author jiyukai

 */

public class Node<Key,Value> {

       //结点键

       public Key key;

      

       //结点值

       public Value value;

      

       //结点左子树

       public Node left;

      

       //结点右子树

       public Node right;

      

       //结点指向父节点的链接颜色,red为true,black为false

       public boolean color;

       public Node(Key key, Value value, Node left, Node right, boolean color) {

              super();

              this.key = key;

              this.value = value;

              this.left = left;

              this.right = right;

              this.color = color;

       }

      

}

      

四、 红黑树平衡化方法

  在对红黑树进行增删改查操作后,很有可能会出现

  1、红链接为右链接

  2、一个结点同时和两条红色链接相连

  这些都是和红黑树的特性不匹配的存在,因此我们需要做一些平衡化的操作,来保证红黑树平衡的同时,又满足既有的特性:

  4.1左旋

  当某个节点的左链接为黑色,右链接为红色,此时需要左旋,左旋的步骤和示意图如下:

   

  1、让当前结点H的右子结点X的左子结点,变为当前结点H的右子结点

  2、让当前结点H成为X的左子结点

  3、让H的color变成X的color

  4、让H的color变为红色

   

  4.2右旋

  当某个节点的左子结点链接是红色,并且左子节点的左子节点链接也是红色,此时需要右旋,右旋的步骤和示意图如下:

   

  1、让H的右子结点成为X的左子节点

  2、让X成为H的右子结点

  3、让H的color变为X的color

  4、让H的color变为red

   

  右旋后发现,当前结点变成了H,此时H的左右子结点的链接都是红色,这是不符合红黑树的特性的,那么需要如何处理呢,见如下的颜色反转方法:

  4.3颜色反转

  当一个结点的左右子结点的链接都是红色,此时只需要把两个红色链接变为黑色,同时使当前结点的链接改为红色即可(根结点除外)。

   

  若当前结点非根结点,则反转后的链接为红色

   

  若当前结点为根结点,则反转后的链接为黑色

   

五、 红黑树平衡化场景

  5.1、向单个2-结点中插入元素

  5.1.1若插入的元素比2-结点小,则新增一个红色链接的结点即可

   

  5.1.2若插入的元素比2-结点大,,则需要左旋处理

   

  左旋后

   

  5.2、向非根结点的2-结点插入新键

  往红黑树中插入C

   

  右链接为红色链接,需要左旋

   

  5.3、向单个3-结点插入新键

  5.3.1 往该3-结点中插入新键,若新键比3-结点中的键都要大

   

   

  出现B的左右链接均为红色,需要做颜色反转

   

  5.3.2往该3-结点中插入新键,若新键比3-结点中的键都要小

   

   

  出现连续两个左子结点为红链接的情况,需要右旋

   

  出现左右两个子结点的链接为红链接的情况,需要做颜色反转

   

  5.3.2往该3-结点中插入新键,若新键介于3-结点两个键之间

   

   

  出现右链接为红色链接的情况,需要左旋

   

  出现连续两个左子结点为红链接的情况,需要右旋

   

  出现左右两个子结点的链接为红链接的情况,需要做颜色反转

   

  5.4、向非根结点的3-结点中插入新键

  往红黑树中插入元素H

   

   

  出现连续两个左子结点为红链接的情况,需要右旋

   

  出现左右两个子结点的链接为红链接的情况,需要做颜色反转

   

  出现右链接为红色链接的情况,需要左旋

   

六、 红黑树的实现

/**

 * 红黑树

 * @author jiyukai

 * @param <Key>

 */

public class RedBlackTree<Key extends Comparable<Key>, Value> {

       // 根结点

       private Node root;

       // 元素个数

       private int N;

       // 红色链接布尔值

       private final static boolean RED = true;

       // 黑色链接布尔值

       private final static boolean BLACK = false;

       /**

        * 判断结点指向父节点的颜色是否为红色

        *

        * @param node

        * @return

        */

       private boolean isRed(Node x) {

              if (null == x) {

                     return false;

              }

              return x.color == RED;

       }

       /**

        * 返回红黑树的结点数量大小

        *

        * @return

        */

       private int size() {

              return N;

       }

       /**

        * 左旋并返回左旋后的根结点

        *

        * @return

        */

       private Node rotateLeft(Node x) {

              // 找出当前结点x的右子结点

              Node xRight = x.right;

              // 找出右子结点的左子结点

              Node xRightl = xRight.left;

              // 让当前结点x的右子结点的左子结点成为当前结点的右子结点

              x.right = xRightl;

              // 让当前结点x称为右子结点的左子结点

              xRight.left = x;

              // 让当前结点x的color变成右子结点的color

              x.color = xRight.color;

              // 让当前结点x的color变为RED

              x.color = RED;

              // 返回当前结点的右子结点

              return xRight;

       }

       /**

        * 右旋并返回右旋后的根结点

        *

        * @return

        */

       private Node rotateRight(Node x) {

              // 找出当前结点x的左子结点

              Node xLeft = x.left;

              // 找出当前结点x的左子结点的右子结点

              Node xLeftr = xLeft.right;

              // 让当前结点x的左子结点的右子结点称为当前结点的左子结点

              x.left = xLeftr;

              // 让当前结点成为左子结点的右子结点

              xLeft.right = x;

              // 让当前结点x的color值成为左子结点的color值

              xLeft.color = x.color;

              // 让当前结点x的color变为RED

              x.color = RED;

              // 返回当前结点的左子结点

              return xLeft;

       }

       /**

        * 颜色反转

        *

        * @param x

        */

       private void flipColors(Node x) {

              // 当前结点的color属性值变为RED;

              x.color = RED;

              // 当前结点的左右子结点的color属性值都变为黑色

              x.left.color = BLACK;

              x.right.color = BLACK;

       }

       /**

        * 存放键值对

        *

        * @param key

        * @param value

        */

       private void put(Key key, Value value) {

              // 根结点开始查找合适的位置存放结点

              root = put(root, key, value);

              // 根结点颜色改为红色

              root.color = RED;

       }

       /**

        * 往指定结点存放键值对,并返回存放后的结点,即新的树

        *

        * @param x

        * @param key

        * @param value

        * @return

        */

       private Node put(Node x, Key key, Value value) {

              if (x == null) {

                     // 总数+1

                     N++;

                     return new Node(key, value, null, null, RED);

              }

              int compare = key.compareTo((Key) x.key);

              if (compare > 0) {

                     // 存放的key大于当前结点,则继续遍历当前结点的右子树

                     x.right = put(x.right, key, value);

              } else if (compare < 0) {

                     // 存放的key小于当前结点,则继续遍历当前结点的左子树

                     x.left = put(x.left, key, value);

              } else {

                     // 存放的key等于当前结点,则替换

                     x.value = value;

              }

              // 当前结点的左链接是黑色,右链接是红色,做左旋处理

              if (isRed(x.right) && !isRed(x.left)) {

                     x = rotateLeft(x);

              }

              // 当前结点的左子节点h和h的左子节点都是红色链接,做右旋处理

              if (isRed(x.left) && isRed(x.left.left)) {

                     x = rotateRight(x);

              }

              // 当前结点的左右链接都是红色,做颜色反转处理

              if (isRed(x.left) && isRed(x.right)) {

                     flipColors(x);

              }

              return x;

       }

       /**

        * 根据Key找到Value

        *

        * @param key

        * @return

        */

       public Value get(Key key) {

              return get(root, key);

       }

       /**

        * 从指定结点开始找key对应的Value

        *

        * @param x

        * @param key

        * @return

        */

       public Value get(Node x, Key key) {

              if (x == null) {

                     return null;

              }

              int compare = key.compareTo((Key) x.key);

              if (compare > 0) {

                     // 查找的key大于当前结点,则继续遍历当前结点的右子树

                     return get(x.right, key);

              } else if (compare < 0) {

                     // 查找的key小于当前结点,则继续遍历当前结点的左子树

                     return get(x.left, key);

              } else {

                     return (Value) x.value;

              }

       }

}

 


发布评论
IT源码网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

数据结构(六):复杂树之2-3树讲解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。