`

红黑树的Java实现

    博客分类：
  • J2SE
JavaUP 
阅读更多

红黑树可能是要考虑情况最多的BST树了，它有自己的规则（见代码的注释），通过这些规则可以保证花费较小的代价来达到相对平衡。
注意，红黑树仍然不是平衡树，但是统计性能要好于AVL树。
要保持红黑树的规则，主要通过两类操作，一类是换色，一类还是旋转。
红黑树插入主要要解决红-红冲突，而删除主要则解决“双黑”

同样，红黑树的删除节点实现是最复杂的，不过，复杂也就在于考虑的情况多，掌握了这几种情况实现还是不困难。
其实，红黑树其实是一颗扩充的二叉树，所以也是满二叉树，其空节点可以看做是扩充的叶节点。但是红黑树的扩充叶节点是有特殊意义的。


下面是代码：

<!---->package  algorithms.tree;

 /**
 * R-B Tree has following four rules:
 * 1)every node is either red or black
 * 2)root and empty node (external leaf node) are always black.
 * 3)the red node's parent node must be black
 * 4)every simple path start from node X to its descendant contains same number of black node
 * 
 * 
 *  @author  yovn
 *
  */
public   class  RBTree < E  extends  Comparable < E >>   extends  DefaultBSTree < E >   implements  BSTree < E >  {

    
    
     public   static   class  RBPrinter < E  extends  Comparable < E >>   implements  DefaultBSTree.NodeVisitor < E >
    {

        @Override
         public   void  visit(E ele) {
            
            
        }

        @Override
         public   void  visitNode(algorithms.tree.DefaultBSTree.BSTNode < E >  node) {
            RBNode < E >  n = (RBNode < E > )node;
             if ( ! n.isNull())
            System.out.print(n.key + " ( " + (n.color == RBNode.RED ? " RED " : " BLACK " ) + " ), " );
            
        }
        
    }
     static   class  RBNode < E  extends  Comparable < E >>   extends  BSTNode < E >
    {



         static   final   boolean  RED = false ;
         static   final   boolean  BLACK = true ;
        
        
        
        RBNode < E >  parent;
         boolean  color; // red or black
        
        
        RBNode(RBNode < E >  p,E key, boolean  color) {
             super (key);
             this .color = color;
             this .parent = p;
            
        }
        
        
        
         final   boolean  isNull(){ return  key == null ;}
        
    }
    
    
        
    @Override
     public   final   boolean  delete(E ele) {
        RBNode < E >  cur;
        
         int  cmp;
         if (root == null ) return   false ;
        cur = (RBNode < E > )root;
         while ( ! cur.isNull() && (cmp = ele.compareTo(cur.key)) != 0 )
        {
             if (cmp < 0 )cur = (RBNode < E > )cur.left;
             else  cur = (RBNode < E > )cur.right;
                
        }
         if (cur.isNull())
        {
             // can't find specified key
             return   false ;
        }
         if ( ! ((RBNode < E > )cur.left).isNull() &&! ((RBNode < E > )cur.right).isNull())
        {
            RBNode < E >  prev = (RBNode < E > )cur.left;
        
             while ( ! ((RBNode < E > )prev.right).isNull())
            {
                
                prev = (RBNode < E > )prev.right;
            }
            cur.key = prev.key;
            cur = prev;
        
        }
         if ( ! ((RBNode < E > )cur.left).isNull())
        {
             if  (cur  ==  root) {
                root  =  cur.left;
                ((RBNode < E > )root).color = RBNode.BLACK;
                 return   true ;
            }
            
             if (cur.parent.left == cur)
            {
                cur.parent.left = cur.left;
                ((RBNode < E > )cur.left).parent = cur.parent;
            }
             else
            {
                cur.parent.right = cur.left;
                ((RBNode < E > )cur.left).parent = cur.parent;
            }
             if (cur.color == RBNode.BLACK)
            {
                ((RBNode < E > )cur.left).color = RBNode.BLACK;
            }
        }
         else   if ( ! ((RBNode < E > )cur.right).isNull())
        {
             if  (cur  ==  root) {
                root  =  cur.right;
                ((RBNode < E > )root).color = RBNode.BLACK;
                 return   true ;
            }
            
             if (cur.parent.left == cur)
            {
                cur.parent.left = cur.right;
                ((RBNode < E > )cur.right).parent = cur.parent;
            }
             else
            {
                cur.parent.right = cur.right;
                ((RBNode < E > )cur.right).parent = cur.parent;
            }
             if (cur.color == RBNode.BLACK)
            {
                ((RBNode < E > )cur.right).color = RBNode.BLACK;
            }
        }
         else
        {
             if (cur == root)
            {
                root = null ;
                 return   true ;
            }
            RBNode < E >  todo;
             if (cur.parent.left == cur)
            {
                todo = newNullNode(cur.parent);
                cur.parent.left = todo;
            }
            
             else
            {
                todo = newNullNode(cur.parent);
                cur.parent.right = todo;
            }
             if (cur.color == RBNode.BLACK)
            {
                 // now todo is a double black node, we will eliminate the double black
                fixup_double_black(todo);
            }
            
        }
        
         return   true ;
    }

    @Override
     public  E findMax() {
         if (isEmpty()) return   null ;
        BSTNode < E >  node = root;
         while ( ! ((RBNode < E > )node.right).isNull())
        {
            node = node.right;
        }
         return  node.key;
    }


    @Override
     public  E findMin() {
         if (isEmpty()) return   null ;
        BSTNode < E >  node = root;
         while ( ! ((RBNode < E > )node.left).isNull())
        {
            node = node.left;
        }
         return  node.key;
    }

     private   final  RBNode < E >  newNullNode(RBNode < E >  p)
    {
         return   new  RBNode < E > (p, null ,RBNode.BLACK);
    }
    
     private   final  RBNode < E >  newNormalNode(RBNode < E >  p,E key,  boolean  color)
    {
        RBNode < E >  node =   new  RBNode < E > (p,key,color);
        node.left = newNullNode(node);
        node.right = newNullNode(node);
         return  node;
    }

     private   final   void  fixup_double_black(RBNode < E >  cur) {
        
        RBNode < E >  sibling;
        RBNode < E >  p;
    
         while (cur != root) // until its parent,parent maybe double black 
        {
            p = cur.parent;
             if (p.left == cur)
            {
                sibling = (RBNode < E > )p.right;
                 if (sibling.color == RBNode.RED)
                {
                    rotate_from_right(p);
                    p.color = RBNode.RED;
                    sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
                     // this case  transformed to another case handled in other place
                }
                 else  
                {
                     if (((RBNode < E > )sibling.right).color == RBNode.RED)
                    {
                        rotate_from_right(p);
                        sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
                        p.color = RBNode.BLACK;
                        ((RBNode < E > )sibling.right).color = RBNode.BLACK;
                         // ok done!
                         return ;
                        
                    }
                     else   if (((RBNode < E > )sibling.left).color == RBNode.RED)
                    {
                        rotate_from_left(sibling);
                        sibling.color = RBNode.RED;
                        sibling.parent.color = RBNode.BLACK; // its parent was previously be its left child, remember we have done a left rotation from sibling
                        
                         //  now transformed to previous case, double black 's sibling(black) have right child colored red
                        
                    }
                     else   //   sibling's two children are both black
                    {
                         // re-coloring the sibling and parent
                        sibling.color = RBNode.RED;
                         if (p.color == RBNode.BLACK)
                        {
                            cur = p;
                             // now the cur node was not double black node ,but p was a double black
                        }
                         else
                        {
                            p.color = RBNode.BLACK; // eliminated the double black node 
                             return ;
                        }
                    }
                }
            }
             else
            {
                sibling = (RBNode < E > )p.left;
                 if (sibling.color == RBNode.RED)
                {
                    rotate_from_left(p);
                    p.color = RBNode.RED;
                    sibling.color = RBNode.BLACK; // actually, p.parent==sibling, remember we have done one rotation
                     // this case  transformed to another case handled in other place
                }
                 else  
                {
                     if (((RBNode < E > )sibling.left).color == RBNode.RED)
                    {
                        rotate_from_left(p);
                        sibling.color = p.color; // also, p.parent==sibling, some textbook say here sibling's color can be red while not violate the 3th rule, i don't think so.
                        p.color = RBNode.BLACK;
                        ((RBNode < E > )sibling.left).color = RBNode.BLACK;
                         // ok done!
                         return ;
                        
                    }
                     else   if (((RBNode < E > )sibling.right).color == RBNode.RED)
                    {
                        rotate_from_right(sibling);
                        sibling.color = RBNode.RED;
                        sibling.parent.color = RBNode.BLACK; // its parent was previously be its right child, remember we have done a left rotation from sibling
                    
                         //  now transformed to previous case, double black 's sibling(black) have right child colored red
                        
                    }
                     else   //   sibling's two children are both black
                    {
                         // re-coloring the sibling and parent
                        sibling.color = RBNode.RED;
                         if (p.color == RBNode.BLACK)
                        {
                            cur = p;
                             // now the cur node was not double black node ,but p was a double black
                        }
                         else
                        {
                            p.color = RBNode.BLACK; // eliminated the double black node 
                             return ;
                        }
                    }
                }
            }
        }
        
    }

    



    @Override
     public   final   void  insert(E ele) {
         if (root == null )
        {
            root = newNormalNode( null ,ele,RBNode.BLACK); // now root's black-height(bh) is 1
             return ;
        }
        RBNode < E >  ret = _insert((RBNode < E > )root,ele); // first insert it
        _insert_fixup(ret); // fix-up the R-B tree from node cur;
    }
    
    
     private   final   void  _insert_fixup(RBNode < E >  cur) {
        
        RBNode < E >  p,g;
    
         // we should fix until it is black colored
         while (cur != root && cur.color == RBNode.RED)
        {
            p = cur.parent;
             if (p.color == RBNode.BLACK)
            {
                 // that's fine, the insertion will not change any black height, and will not violate any rule.
                 return ;
            }
            g = p.parent; // we can assume the p is not null now.
            
             if (p == g.left)
            {
                RBNode < E >  uncle = (RBNode < E >  )g.right;
                 if (uncle.color == RBNode.RED)
                {
                     // re-coloring
                    g.color = RBNode.RED;
                    uncle.color = p.color = RBNode.BLACK;
                    
                     // now the g maybe conflict with its parent;
                    cur = g;
                }
                 else
                {
                     if (cur == p.right)
                    {
                         // this case we should do left rotation, and then it will transform to next case
                        cur = rotate_from_right(p);
                        cur = (RBNode < E > )cur.left;
                         // transformed to next case    
                    }
                    
                    cur = rotate_from_left(g);
                    cur.color = RBNode.BLACK;
                    ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
                                    
                
                }
                
            }
             else
            {
                RBNode < E >  uncle = (RBNode < E >  )g.left;
                 if (uncle.color == RBNode.RED)
                {
                     // re-coloring
                    g.color = RBNode.RED;
                    uncle.color = p.color = RBNode.BLACK;
                    
                     // now the g maybe conflict with its parent;
                    cur = g;
                }
                 else
                {
                     if (cur == p.left)
                    {
                         // this case we should do right rotation, and then it will transform to next case
                        cur = rotate_from_left(p);
                        cur = (RBNode < E > )cur.right;
                         // transformed to next case    
                    }
                    
                    cur = rotate_from_right(g);
                    cur.color = RBNode.BLACK;
                    ((RBNode < E > )cur.left).color = ((RBNode < E > )cur.right).color = RBNode.RED;
                                    
                
                }
            }
                
        }
        ((RBNode < E > )root).color = RBNode.BLACK;
        
        
    }




     private   final  RBNode < E >  rotate_from_right(RBNode < E >  p) {
        
        RBNode < E >  g = p.parent;
        RBNode < E >  cur = (RBNode < E > )p.right;
        
        p.right = cur.left;
         if (cur.left != null )((RBNode < E > )cur.left).parent = p;
        
        cur.left = p;
        p.parent = cur;
        
        
         if (g != null )
        {
             if (g.left == p)g.left = cur;
             else  g.right = cur;
        }
         else  root = cur;
        
        cur.parent = g;
         return  cur;
        
    
    }




     private   final  RBNode < E >  rotate_from_left(RBNode < E >  p) {
        RBNode < E > co
分享到：
| 排序算法复习（Java实现）(二）： 归并排 ...
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    红黑树Java实现

    - Java集合框架：`TreeMap`和`TreeSet`是基于红黑树实现的，提供有序的元素存储和高效的查找、插入和删除操作。 - 数据库索引：数据库系统如MySQL的InnoDB存储引擎使用红黑树作为索引结构。 - C++标准模板库(STL)...

    红黑树java实现

    ### 红黑树Java实现详解 #### 一、红黑树简介 红黑树（Red-Black Tree）是一种自平衡二叉查找树。在计算机科学中，它被广泛应用于各种场景，比如作为关联数组的底层实现。红黑树通过在每个节点上存储一个额外的位...

    红黑树的Java实现参考源码

    在Java实现中，红黑树的核心类是`java.util.TreeMap.Node`，这个类代表树中的一个节点，包含键值对以及颜色属性。插入操作会遵循以下步骤： 1. 首先，新插入的节点默认为红色，因为红色节点不会破坏红黑树的性质。 ...

    java实现红黑树

    总结来说，这个Java实现的红黑树通过OrdRow.java和OrdDataSet.java两个类，实现了红黑树的基本操作，包括插入、删除、查找和遍历，并严格遵循了红黑树的五条性质，以确保高效的数据操作。学习这个实现有助于理解红黑...

    Java实现的红黑树

    红黑树（Red-Black Tree）是一种自平衡的二叉查找树，由计算机科学家Rudolf Bayer在1972年提出。...通过分析和实现Java中的红黑树，我们可以深入理解这种数据结构的工作原理及其在实际应用中的价值。

    java-红黑树-代码实现（一）

    在本篇博客中，我们将探讨红黑树的原理以及如何用Java实现。 首先，我们来理解红黑树的基本概念： 1. 每个节点都有颜色属性，可以是红色或黑色。 2. 根节点是黑色。 3. 所有叶子节点（NIL或空节点）都是黑色。 4. ...

    红黑树java操作代码 红黑树是java里面遍历性能最好数据结构

    在Java中，虽然标准库并未直接提供红黑树的类，但我们可以自定义实现，如提供的`RedBlackTree.java`和`tetsRed.java`文件所示。下面将详细介绍红黑树的概念、性质以及如何在Java中实现它。 **1. 红黑树的概念** ...

    JAVA实现的红黑树

    提供的文件"EightRBtree"可能是一个实现了红黑树的Java类库，它可能包含了红黑树的插入、删除和查找等基本操作的实现。具体实现细节可能包括如何处理节点的颜色、如何进行旋转调整以及如何维护红黑树的平衡。 在...

    红黑树的java实现 （二叉树也有）

    在Java中，虽然没有直接提供红黑树的类，但`java.util.TreeMap`和`java.util.TreeSet`底层就是通过红黑树实现的。它们提供了高效的键值对存储和集合管理，支持有序操作，如按自然顺序或自定义比较器进行排序。 当...

    红黑树实现java代码

    红黑树实现java代码，供大家参考，具体详解请参见我的博客http://blog.csdn.net/clamclam/article/details/49545477

    java实现的红黑树

    在Java中，红黑树被广泛应用于`java.util.TreeMap`、`java.util.TreeSet`以及`java.util.HashMap`的内部实现中。 1. **红黑树的基本性质** - 每个节点不是红色就是黑色。 - 根节点是黑色。 - 所有叶子节点（NIL...

    红黑树的插入-java实现

    在Java中实现红黑树，通常会定义一个表示节点的类，包含节点值、颜色、父节点、左右子节点等属性，并提供插入、旋转、颜色翻转等方法。具体实现时，需要注意以下几点： - 插入过程中，需要维护节点的平衡状态，以...

    红黑树实现源码

    红黑树因其高效性能在许多实际应用中得到采用，如C++标准模板库(STL)中的set和map容器，以及Java的TreeMap和TreeSet类。它们使用红黑树作为底层数据结构，提供快速的查找、插入和删除操作。 5. 红黑树的优势： - ...

    红黑树-基于Java实现的红黑树数据结构.zip

    5. **Java实现**： - Java标准库中的`java.util.TreeMap`和`java.util.TreeSet`类底层就是用红黑树实现的。 - 实现红黑树需要定义节点类，包含节点值、颜色、左子节点、右子节点以及父节点等属性，并实现插入、...

    Java-Red-Black-Tree:Java中通用红黑树的实现

    在Java中，红黑树的实现位于`java.util.TreeMap`和`java.util.TreeSet`的源码中，具体可以查看`java.util.TreeMap$Node`类，这个类代表了红黑树的节点，包含了颜色属性、键、值和子节点等信息。通过分析源码，我们...

    java 树的数据结构 红黑树的实现 学习路线

    本文将深入探讨Java中树的数据结构，特别是红黑树的实现，以及如何构建一个有效的学习路线。 首先，让我们从"树的基本概念"开始。树是一种非线性的数据结构，它由节点（或称为顶点）和边构成，每个节点可以有零个或...

    通过Java实现红黑树及其可视化

    通过Java实现红黑树及其可视化 对于节点的定义，包含节点的数值、节点的颜色、节点的父节点、节点的左右叶子结点 通过Java实现红黑树，包括红黑树的插入操作、删除操作、维护红黑树性质的操作以及常用的方法函数...

    红黑树、平衡二叉树、排序算法的java实现

    本文将深入探讨"红黑树"、"平衡二叉树"、"二叉树"、"二叉搜索树"以及"排序算法"这些关键概念，并在Java环境下进行实现。 首先，我们来理解"二叉树"。二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，...

    红黑树和AVL树的实现

    红黑树的平衡要求相对较宽松，插入和删除操作的代价较低，且在实践中表现良好，是许多语言标准库如Java和C++的默认选择。 在实际应用中，如果对查找速度有较高要求，可以选择AVL树；而如果更注重插入和删除的效率，...

    红黑树编程实现

    在这个“红黑树编程实现”的课程设计中，我们将深入探讨这种数据结构的原理、特性以及如何通过编程实现。 首先，我们要理解红黑树的基本概念。红黑树的每个节点都有两个属性：颜色（红色或黑色）和键值。它遵循以下...

Magicbox
Global site tag (gtag.js) - Google Analytics