首页 > 代码库 > 红黑树,TreeMap,插入操作

红黑树,TreeMap,插入操作

红黑树                                                                                 

红黑树顾名思义就是节点是红色或者黑色的平衡二叉树,它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则:

1、每个节点都只能是红色或者黑色

2、根节点是黑色

3、每个叶节点(NIL节点,空节点)是黑色的。

4、如果一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。

5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。所以红黑树它是复杂而高效的,其检索效率O(log n)。

红黑树的插入操作                                                                    

如果插入第一个节点,我们直接用树根记录这个节点,并设置为黑色,否则作递归查找插入。

默认插入的节点颜色都是红色,因为插入黑色节点会破坏根路径上的黑色节点总数,但即使如此,也会出现连续红色节点的情况。因此在一般的插入操作之后,出现红黑树约束条件不满足的情况(称为失去平衡)时,就必须要根据当前的红黑树的情况做相应的调整。和AVL树的平衡调整通过旋转操作的实现类似,红黑树的调整操作一般都是通过旋转结合节点的变色操作来完成的。

  • 叔父节点是黑色(若是空节点则默认为黑色)

这种情况下通过旋转和变色操作可以使红黑树恢复平衡。但是考虑当前节点n和父节点p的位置又分为四种情况:

A、n是p左子节点,p是g的左子节点。

B、n是p右子节点,p是g的右子节点。

C、n是p左子节点,p是g的右子节点。

D、n是p右子节点,p是g的左子节点。

  • 情况A:n是p左子节点,p是g的左子节点。针对该情况可以通过一次右旋转操作,并将p设为黑色,g设为红色完成重新平衡。

1

右旋操作的步骤是将p挂接在g节点原来的位置(如果g原是根节点,需要考虑边界条件),将p的右子树x挂到g的左子节点,再把g挂在p的右子节点上,完成右旋操作。这里将最终旋转结果的子树的根节点作为旋转轴(p节点),也就是说旋转轴在旋转结束后称为新子树的根节点!

  • 情况B则需要使用左单旋操作来解决平衡问题,方法和情况A类似。

2

  • 情况C:n是p左子节点,p是g的右子节点。针对该情况通过一次左旋,一次右旋操作(旋转轴都是n,注意不是p),并将n设为黑色,g设为红色完成重新平衡。

3

需要注意的是,由于此时新插入的节点是n,它的左右子树x,y都是空节点,但即使如此,旋转操作的结果需要将x,y新的位置设置正确(如果不把p和g的对应分支设置为空节点的话,就会破坏树的结构)。在之后的其他操作中,待旋转的节点n的左右子树可能就不是空节点了。

  • 情况D则需要使用一次右单旋,一次左单旋操作来解决平衡问题,方法和情况C类似。

4

  • 叔父节点是红色

当叔父节点是红色时,则不能直接通过上述方式处理了(把前边的所有情况的u节点看作红色,会发现节点u和g是红色冲突的)。但是我们可以交换g与p,u节点的颜色完成当前冲突的解决。

5

但是仅仅这样做颜色交换是不够的,因为祖父节点g的父节点(记作gp)如果也是红色的话仍然会有冲突(g和gp是连续的红色,违反规则2)。为了解决这样的冲突,我们需要从当前插入点n向根节点root回溯两次。

第一次回溯时处理所有拥有两个红色节点的节点,并按照上图中的方式交换父节点g与子节点p,u的颜色,并暂时忽略gp和p的颜色冲突。如果根节点的两个子节点也是这种情况,则在颜色交换完毕后重新将根节点设置为黑色。

第二次回溯专门处理连续的红色节点冲突。由于经过第一遍的处理,在新插入点n的路径上一定不存在同为红色的兄弟节点了。而仍出现gp和p的红色冲突时,gp的兄弟节点(gu)可以断定为黑色,这样就回归前边讨论的叔父节点为黑色时的情况处理。

6

由于发生冲突的两个红色节点位置可能是任意的,因此会出现上述的四种旋转情况。不过我们把靠近叶子的红色节点(g)看作新插入的节点,这样面对A,B情况则把p的父节点gp作为旋转轴,旋转后gp会是新子树的根,而面对C,D情况时把p作为旋转轴即可,旋转后p为新子树的根(因此可以把四种旋转方式封装起来)。

在第二次回溯时,虽然每次遇到红色冲突旋转后都会提升g和gp节点的位置(与根节点的距离减少),但是无论g和gp谁是新子树的根都不会影响新插入节点n到根节点root路径的回溯,而且一旦新子树的根到达根节点(parent指针为空)就可以停止回溯了。

TreeMap数据结构                                                                    

public class TreeMap<K,V>    extends AbstractMap<K,V>    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap继承AbstractMap,实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合, NavigableMap则意味着它支持一系列的导航方法,具备针对给定搜索目标返回最接近匹配项的导航方法 。

TreeMap中同时也包含了如下几个重要的属性:

        //比较器,因为TreeMap是有序的,通过comparator接口我们可以对TreeMap的内部排序进行精密的控制        private final Comparator<? super K> comparator;        //TreeMap红-黑节点,为TreeMap的内部类        private transient Entry<K,V> root = null;        //容器大小        private transient int size = 0;        //TreeMap修改次数        private transient int modCount = 0;        //红黑树的节点颜色--红色        private static final boolean RED = false;        //红黑树的节点颜色--黑色        private static final boolean BLACK = true;

对于叶子节点Entry是TreeMap的内部类,它有几个重要的属性:

//        K key;        //        V value;        //左孩子        Entry<K,V> left = null;        //右孩子        Entry<K,V> right = null;        //父亲        Entry<K,V> parent;        //颜色        boolean color = BLACK;

TreeMap put()方法                                                                   

在TreeMap的put()的实现方法中主要分为两个步骤,第一:构建排序二叉树,第二:平衡二叉树

对于排序二叉树的创建,其添加节点的过程如下:

1、以根节点为初始节点进行检索。

2、与当前节点进行比对,若新增节点值较大,则以当前节点的右子节点作为新的当前节点。否则以当前节点的左子节点作为新的当前节点。

3、循环递归2步骤知道检索出合适的叶子节点为止。

4、将新增节点与3步骤中找到的节点进行比对,如果新增节点较大,则添加为右子节点;否则添加为左子节点。

      public V put(K key, V value) {             //用t表示二叉树的当前节点              Entry<K,V> t = root;              //t为null表示一个空树,即TreeMap中没有任何元素,直接插入              if (t == null) {                  //比较key值,个人觉得这句代码没有任何意义,空树还需要比较、排序?                  compare(key, key); // type (and possibly null) check                  //将新的key-value键值对创建为一个Entry节点,并将该节点赋予给root                  root = new Entry<>(key, value, null);                  //容器的size = 1,表示TreeMap集合中存在一个元素                  size = 1;                  //修改次数 + 1                  modCount++;                  return null;              }              int cmp;     //cmp表示key排序的返回结果              Entry<K,V> parent;   //父节点              // split comparator and comparable paths              Comparator<? super K> cpr = comparator;    //指定的排序算法              //如果cpr不为空,则采用既定的排序算法进行创建TreeMap集合              if (cpr != null) {                  do {                      parent = t;      //parent指向上次循环后的t                      //比较新增节点的key和当前节点key的大小                      cmp = cpr.compare(key, t.key);                      //cmp返回值小于0,表示新增节点的key小于当前节点的key,则以当前节点的左子节点作为新的当前节点                      if (cmp < 0)                          t = t.left;                      //cmp返回值大于0,表示新增节点的key大于当前节点的key,则以当前节点的右子节点作为新的当前节点                      else if (cmp > 0)                          t = t.right;                      //cmp返回值等于0,表示两个key值相等,则新值覆盖旧值,并返回新值                      else                          return t.setValue(value);                  } while (t != null);              }              //如果cpr为空,则采用默认的排序算法进行创建TreeMap集合              else {                  if (key == null)     //key值为空抛出异常                      throw new NullPointerException();                  /* 下面处理过程和上面一样 */                  Comparable<? super K> k = (Comparable<? super K>) key;                  do {                      parent = t;                      cmp = k.compareTo(t.key);                      if (cmp < 0)                          t = t.left;                      else if (cmp > 0)                          t = t.right;                      else                          return t.setValue(value);                  } while (t != null);              }              //将新增节点当做parent的子节点              Entry<K,V> e = new Entry<>(key, value, parent);              //如果新增节点的key小于parent的key,则当做左子节点              if (cmp < 0)                  parent.left = e;            //如果新增节点的key大于parent的key,则当做右子节点              else                  parent.right = e;              /*               *  上面已经完成了排序二叉树的的构建,将新增节点插入该树中的合适位置               *  下面fixAfterInsertion()方法就是对这棵树进行调整、平衡,具体过程参考上面的五种情况               */              fixAfterInsertion(e);              //TreeMap元素数量 + 1              size++;              //TreeMap容器修改次数 + 1              modCount++;              return null;          }

上面代码中do{}代码块是实现排序二叉树的核心算法,通过该算法我们可以确认新增节点在该树的正确位置。找到正确位置后将插入即可,这样做了其实还没有完成,因为我知道TreeMap的底层实现是红黑树,红黑树是一棵平衡排序二叉树,普通的排序二叉树可能会出现失衡的情况,所以下一步就是要进行调整。fixAfterInsertion(e); 调整的过程务必会涉及到红黑树的左旋、右旋、着色三个基本操作。代码如下:

     /**       * 新增节点后的修复操作        * x 表示新增节点        */       private void fixAfterInsertion(Entry<K,V> x) {              x.color = RED;    //新增节点的颜色为红色                //循环 直到 x不是根节点,且x的父节点不为红色              while (x != null && x != root && x.parent.color == RED) {                  //如果X的父节点(P)是其父节点的父节点(G)的左节点                  if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {                      //获取X的叔节点(U)                      Entry<K,V> y = rightOf(parentOf(parentOf(x)));                      //如果X的叔节点(U) 为红色                      if (colorOf(y) == RED) {                               //将X的父节点(P)设置为黑色                          setColor(parentOf(x), BLACK);                          //将X的叔节点(U)设置为黑色                          setColor(y, BLACK);                          //将X的父节点的父节点(G)设置红色                          setColor(parentOf(parentOf(x)), RED);                          x = parentOf(parentOf(x));                      }                      //如果X的叔节点(U为黑色)                      else {                             //如果X节点为其父节点(P)的右子树,则进行左旋转                          if (x == rightOf(parentOf(x))) {                              //将X的父节点作为X                              x = parentOf(x);                              //右旋转                              rotateLeft(x);                          }  //将X的父节点(P)设置为黑色                          setColor(parentOf(x), BLACK);                          //将X的父节点的父节点(G)设置红色                          setColor(parentOf(parentOf(x)), RED);                          //以X的父节点的父节点(G)为中心右旋转                          rotateRight(parentOf(parentOf(x)));                      }                  }                  //如果X的父节点(P)是其父节点的父节点(G)的右节点                  else {                      //获取X的叔节点(U)                      Entry<K,V> y = leftOf(parentOf(parentOf(x)));                    //如果X的叔节点(U) 为红色                     if (colorOf(y) == RED) {                          //将X的父节点(P)设置为黑色                          setColor(parentOf(x), BLACK);                          //将X的叔节点(U)设置为黑色                          setColor(y, BLACK);                          //将X的父节点的父节点(G)设置红色                          setColor(parentOf(parentOf(x)), RED);                          x = parentOf(parentOf(x));                      }                    //如果X的叔节点(U为黑色);这里会存在两种情况                      else {                          //如果X节点为其父节点(P)的右子树,则进行左旋转                         if (x == leftOf(parentOf(x))) {                              //将X的父节点作为X                              x = parentOf(x);                             //右旋转                              rotateRight(x);                          }                          //(情况五)                          //将X的父节点(P)设置为黑色                          setColor(parentOf(x), BLACK);                          //将X的父节点的父节点(G)设置红色                          setColor(parentOf(parentOf(x)), RED);                          //以X的父节点的父节点(G)为中心右旋转                          rotateLeft(parentOf(parentOf(x)));                      }                  }              }              //将根节点G强制设置为黑色              root.color = BLACK;          }
  • 对这段代码的研究我们发现,其处理过程完全符合红黑树新增节点的处理过程。所以在看这段代码的过程一定要对红黑树的新增节点过程有了解。在这个代码中还包含几个重要的操作。左旋(rotateLeft())、右旋(rotateRight())、着色(setColor())。

  • 左旋:rotateLeft()

  • 所谓左旋转,就是将新增节点(N)当做其父节点(P),将其父节点P当做新增节点(N)的左子节点。即:G.left ---> N ,N.left ---> P。

private void rotateLeft(Entry<K,V> p) {          if (p != null) {              //获取P的右子节点,其实这里就相当于新增节点N(情况四而言)              Entry<K,V> r = p.right;              //将R的左子树设置为P的右子树              p.right = r.left;              //若R的左子树不为空,则将P设置为R左子树的父亲              if (r.left != null)                  r.left.parent = p;              //将P的父亲设置R的父亲              r.parent = p.parent;              //如果P的父亲为空,则将R设置为跟节点              if (p.parent == null)                  root = r;              //如果P为其父节点(G)的左子树,则将R设置为P父节点(G)左子树              else if (p.parent.left == p)                  p.parent.left = r;              //否则R设置为P的父节点(G)的右子树              else                  p.parent.right = r;              //将P设置为R的左子树              r.left = p;              //将R设置为P的父节点              p.parent = r;          }      }

右旋:rotateRight()

所谓右旋转即,P.right ---> G、G.parent ---> P。

private void rotateRight(Entry<K,V> p) {          if (p != null) {              //将L设置为P的左子树              Entry<K,V> l = p.left;              //将L的右子树设置为P的左子树              p.left = l.right;              //若L的右子树不为空,则将P设置L的右子树的父节点              if (l.right != null)                   l.right.parent = p;              //将P的父节点设置为L的父节点              l.parent = p.parent;              //如果P的父节点为空,则将L设置根节点              if (p.parent == null)                  root = l;              //若P为其父节点的右子树,则将L设置为P的父节点的右子树              else if (p.parent.right == p)                  p.parent.right = l;              //否则将L设置为P的父节点的左子树              else                   p.parent.left = l;              //将P设置为L的右子树              l.right = p;              //将L设置为P的父节点              p.parent = l;          }      }

我是天王盖地虎的分割线                                                             

 

 

 

参考:http://blog.csdn.net/chenssy/article/details/26668941

红黑树,TreeMap,插入操作