java算法实现红黑树完整代码示例-6ren

java算法实现红黑树完整代码示例

转载作者：qq735679552 更新时间：2022-09-28 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章java算法实现红黑树完整代码示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

红黑树。

定义。

红黑树（英语：red–black tree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组.

红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树:

红链接均为左链接；没有任何一个结点同时和两条红链接相连；该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同.

满足这样定义的红黑树和相应的2-3树是一一对应的.

java算法实现红黑树完整代码示例

旋转。

旋转又分为左旋和右旋。通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。对比操作前后，可以看出，该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上.

左旋操作如下图:

java算法实现红黑树完整代码示例

右旋旋操作如下图:

java算法实现红黑树完整代码示例

即:

java算法实现红黑树完整代码示例

复杂度。

红黑树的平均高度大约为lgn.

下图是红黑树在各种情况下的时间复杂度，可以看出红黑树是2-3查找树的一种实现，他能保证最坏情况下仍然具有对数的时间复杂度.

java算法实现红黑树完整代码示例

java代码。

 
    ? 
   
         import 
         java.util.nosuchelementexception; 
        
         import 
         java.util.scanner; 
        
         public 
         class 
         redblackbst<key  
         extends 
         = 
         "" 
         key= 
         "" 
         >, value> { 
        
         private 
         static 
         final 
         boolean 
         red =  
         true 
         ; 
        
         private 
         static 
         final 
         boolean 
         black =  
         false 
         ; 
        
         private 
         node root;  
         //root of the bst 
        
         private 
         class 
         node { 
        
         private 
         key key;       
         //key 
        
         private 
         value val;      
         //associated data 
        
         private 
         node left, right;   
         //links to left and right subtrees 
        
         private 
         boolean 
         color;    
         //color of parent link 
        
         private 
         int 
         size;       
         //subtree count 
        
         public 
         node(key key, value val,  
         boolean 
         color,  
         int 
         size) { 
        
         this 
         .key = key; 
        
         this 
         .val = val; 
        
         this 
         .color = color; 
        
         this 
         .size = size; 
        
         } 
        
         } 
        
         //is node x red? 
        
         private 
         boolean 
         isred(node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         false 
         ; 
        
         } 
        
         return 
         x.color == red; 
        
         } 
        
         //number of node in subtree rooted at x; 0 if x is null 
        
         private 
         int 
         size(node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         0 
         ; 
        
         } 
        
         return 
         x.size; 
        
         }   
        
         /** 
        
         * return the number of key-value pairs in this symbol table 
        
         * @return the number of key-value pairs in this symbol table 
        
         */ 
        
         public 
         int 
         size() { 
        
         return 
         size(root); 
        
         } 
        
         /** 
        
         * is this symbol table empty? 
        
         * @return true if this symbol table is empty and false otherwise 
        
         */ 
        
         public 
         boolean 
         isempty() { 
        
         return 
         root ==  
         null 
         ; 
        
         } 
        
         /** 
        
         * return the value associated with the given key 
        
         * @param key the key 
        
         * @return the value associated with the given key if the key is in the symbol table, and null if it is not. 
        
         */ 
        
         public 
         value get(key key) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "argument to get() is null" 
         ); 
        
         } 
        
         return 
         get(root, key); 
        
         } 
        
         //value associated with the given key in subtree rooted at x; null if no such key 
        
         private 
         value get(node x, key key) { 
        
         while 
         (x !=  
         null 
         ) { 
        
         int 
         cmp = key.compareto(x.key); 
        
         if 
         (cmp <  
         0 
         ) { 
        
         x = x.left; 
        
         } 
        
         else 
         if 
         (cmp >  
         0 
         ) { 
        
         x = x.right; 
        
         } 
        
         else 
         { 
        
         return 
         x.val; 
        
         }         
        
         } 
        
         return 
         null 
         ; 
        
         } 
        
         /** 
        
         * does this symbol table contain the given key? 
        
         * @param key the key 
        
         * @return true if this symbol table contains key and false otherwise 
        
         */ 
        
         public 
         boolean 
         contains(key key) { 
        
         return 
         get(key) !=  
         null 
         ; 
        
         } 
        
         /*************************************************************************** 
        
         * red-black tree insertion. 
        
         ***************************************************************************/ 
        
         /** 
        
         * inserts the specified key-value pair into the symbol table, overwriting the old  
        
         * value with the new value if the symbol table already contains the specified key. 
        
         * deletes the specified key (and its associated value) from this symbol table 
        
         * if the specified value is null. 
        
         * 
        
         * @param key the key 
        
         * @param val the value 
        
         * @throws nullpointerexception if key is null 
        
         */ 
        
         public 
         void 
         put(key key, value val) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "first argument to put() is null" 
         ); 
        
         } 
        
         if 
         (val ==  
         null 
         ) { 
        
         delete(key); 
        
         return 
         ; 
        
         } 
        
         root = put(root, key, val); 
        
         root.color = black;     
        
         } 
        
         // insert the key-value pair in the subtree rooted at h 
        
         private 
         node put(node h, key key, value val) { 
        
         if 
         (h ==  
         null 
         ) { 
        
         return 
         new 
         node(key, val, red,  
         1 
         ); 
        
         } 
        
         int 
         cmp = key.compareto(h.key); 
        
         if 
         (cmp <  
         0 
         ) { 
        
         h.left = put(h.left, key, val); 
        
         } 
        
         else 
         if 
         (cmp >  
         0 
         ) { 
        
         h.right = put(h.right, key, val); 
        
         } 
        
         else 
         { 
        
         h.val = val; 
        
         } 
        
         if 
         (isred(h.right) && !isred(h.left)) { 
        
         h = rotateleft(h); 
        
         } 
        
         if 
         (isred(h.left) && isred(h.left.left)) { 
        
         h = rotateright(h); 
        
         } 
        
         if 
         (isred(h.left) && isred(h.right)) { 
        
         flipcolors(h); 
        
         } 
        
         h.size = size(h.left) + size(h.right) +  
         1 
         ; 
        
         return 
         h; 
        
         } 
        
         /*************************************************************************** 
        
         * red-black tree deletion. 
        
         ***************************************************************************/ 
        
         /** 
        
         * removes the smallest key and associated value from the symbol table. 
        
         * @throws nosuchelementexception if the symbol table is empty 
        
         */ 
        
         public 
         void 
         deletemin() { 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "bst underflow" 
         ); 
        
         } 
        
         // if both children of root are black, set root to red 
        
         if 
         (!isred(root.left) && !isred(root.right)) 
        
         root.color = red; 
        
         root = deletemin(root); 
        
         if 
         (!isempty()) root.color = black; 
        
         // assert check(); 
        
         } 
        
         // delete the key-value pair with the minimum key rooted at h 
        
         // delete the key-value pair with the minimum key rooted at h 
        
         private 
         node deletemin(node h) {  
        
         if 
         (h.left ==  
         null 
         ){ 
        
         return 
         null 
         ; 
        
         } 
        
         if 
         (!isred(h.left) && !isred(h.left.left)) { 
        
         h = moveredleft(h); 
        
         } 
        
         h.left = deletemin(h.left); 
        
         return 
         balance(h); 
        
         } 
        
         /** 
        
         * removes the largest key and associated value from the symbol table. 
        
         * @throws nosuchelementexception if the symbol table is empty 
        
         */ 
        
         public 
         void 
         deletemax() { 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "bst underflow" 
         ); 
        
         } 
        
         // if both children of root are black, set root to red 
        
         if 
         (!isred(root.left) && !isred(root.right)) 
        
         root.color = red; 
        
         root = deletemax(root); 
        
         if 
         (!isempty()) root.color = black; 
        
         // assert check(); 
        
         } 
        
         // delete the key-value pair with the maximum key rooted at h 
        
         // delete the key-value pair with the maximum key rooted at h 
        
         private 
         node deletemax(node h) {  
        
         if 
         (isred(h.left)) 
        
         h = rotateright(h); 
        
         if 
         (h.right ==  
         null 
         ) 
        
         return 
         null 
         ; 
        
         if 
         (!isred(h.right) && !isred(h.right.left)) 
        
         h = moveredright(h); 
        
         h.right = deletemax(h.right); 
        
         return 
         balance(h); 
        
         } 
        
         /** 
        
         * remove the specified key and its associated value from this symbol table    
        
         * (if the key is in this symbol table).   
        
         * 
        
         * @param key the key 
        
         * @throws nullpointerexception if key is null 
        
         */ 
        
         public 
         void 
         delete(key key) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "argument to delete() is null" 
         ); 
        
         } 
        
         if 
         (!contains(key)) { 
        
         return 
         ; 
        
         } 
        
         //if both children of root are black, set root to red 
        
         if 
         (!isred(root.left) && !isred(root.right)) { 
        
         root.color = red; 
        
         } 
        
         root = delete(root, key); 
        
         if 
         (!isempty()) { 
        
         root.color = black; 
        
         } 
        
         } 
        
         // delete the key-value pair with the given key rooted at h 
        
         // delete the key-value pair with the given key rooted at h 
        
         private 
         node delete(node h, key key) { 
        
         if 
         (key.compareto(h.key) <  
         0 
         ) { 
        
         if 
         (!isred(h.left) && !isred(h.left.left)) { 
        
         h = moveredleft(h); 
        
         } 
        
         h.left = delete(h.left, key); 
        
         } 
        
         else 
         { 
        
         if 
         (isred(h.left)) { 
        
         h = rotateright(h); 
        
         } 
        
         if 
         (key.compareto(h.key) ==  
         0 
         && (h.right ==  
         null 
         )) { 
        
         return 
         null 
         ; 
        
         } 
        
         if 
         (!isred(h.right) && !isred(h.right.left)) { 
        
         h = moveredright(h); 
        
         } 
        
         if 
         (key.compareto(h.key) ==  
         0 
         ) { 
        
         node x = min(h.right); 
        
         h.key = x.key; 
        
         h.val = x.val; 
        
         h.right = deletemin(h.right); 
        
         } 
        
         else 
         { 
        
         h.right = delete(h.right, key); 
        
         } 
        
         } 
        
         return 
         balance(h); 
        
         } 
        
         /*************************************************************************** 
        
         * red-black tree helper functions. 
        
         ***************************************************************************/ 
        
         // make a left-leaning link lean to the right 
        
         // make a left-leaning link lean to the right 
        
         private 
         node rotateright(node h) { 
        
         // assert (h != null) && isred(h.left); 
        
         node x = h.left; 
        
         h.left = x.right; 
        
         x.right = h; 
        
         x.color = x.right.color; 
        
         x.right.color = red; 
        
         x.size = h.size; 
        
         h.size = size(h.left) + size(h.right) +  
         1 
         ; 
        
         return 
         x; 
        
         } 
        
         // make a right-leaning link lean to the left 
        
         // make a right-leaning link lean to the left 
        
         private 
         node rotateleft(node h) { 
        
         // assert (h != null) && isred(h.right); 
        
         node x = h.right; 
        
         h.right = x.left; 
        
         x.left = h; 
        
         x.color = x.left.color; 
        
         x.left.color = red; 
        
         x.size = h.size; 
        
         h.size = size(h.left) + size(h.right) +  
         1 
         ; 
        
         return 
         x; 
        
         } 
        
         // flip the colors of a node and its two children 
        
         // flip the colors of a node and its two children 
        
         private 
         void 
         flipcolors(node h) { 
        
         // h must have opposite color of its two children 
        
         // assert (h != null) && (h.left != null) && (h.right != null); 
        
         // assert (!isred(h) && isred(h.left) && isred(h.right)) 
        
         //  || (isred(h) && !isred(h.left) && !isred(h.right)); 
        
         h.color = !h.color; 
        
         h.left.color = !h.left.color; 
        
         h.right.color = !h.right.color; 
        
         } 
        
         // assuming that h is red and both h.left and h.left.left 
        
         // are black, make h.left or one of its children red. 
        
         // assuming that h is red and both h.left and h.left.left 
        
         // are black, make h.left or one of its children red. 
        
         private 
         node moveredleft(node h) { 
        
         // assert (h != null); 
        
         // assert isred(h) && !isred(h.left) && !isred(h.left.left); 
        
         flipcolors(h); 
        
         if 
         (isred(h.right.left)) {  
        
         h.right = rotateright(h.right); 
        
         h = rotateleft(h); 
        
         flipcolors(h); 
        
         } 
        
         return 
         h; 
        
         } 
        
         // assuming that h is red and both h.right and h.right.left 
        
         // are black, make h.right or one of its children red. 
        
         // assuming that h is red and both h.right and h.right.left 
        
         // are black, make h.right or one of its children red. 
        
         private 
         node moveredright(node h) { 
        
         // assert (h != null); 
        
         // assert isred(h) && !isred(h.right) && !isred(h.right.left); 
        
         flipcolors(h); 
        
         if 
         (isred(h.left.left)) {  
        
         h = rotateright(h); 
        
         flipcolors(h); 
        
         } 
        
         return 
         h; 
        
         } 
        
         // restore red-black tree invariant 
        
         // restore red-black tree invariant 
        
         private 
         node balance(node h) { 
        
         // assert (h != null); 
        
         if 
         (isred(h.right)) { 
        
         h = rotateleft(h); 
        
         } 
        
         if 
         (isred(h.left) && isred(h.left.left)) { 
        
         h = rotateright(h); 
        
         } 
        
         if 
         (isred(h.left) && isred(h.right)) { 
        
         flipcolors(h); 
        
         } 
        
         h.size = size(h.left) + size(h.right) +  
         1 
         ; 
        
         return 
         h; 
        
         } 
        
         /*************************************************************************** 
        
         * utility functions. 
        
         ***************************************************************************/ 
        
         /** 
        
         * returns the height of the bst (for debugging). 
        
         * @return the height of the bst (a 1-node tree has height 0) 
        
         */ 
        
         public 
         int 
         height() { 
        
         return 
         height(root); 
        
         } 
        
         private 
         int 
         height(node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         - 
         1 
         ; 
        
         } 
        
         return 
         1 
         + math.max(height(x.left), height(x.right)); 
        
         } 
        
         /*************************************************************************** 
        
         * ordered symbol table methods. 
        
         ***************************************************************************/ 
        
         /** 
        
         * returns the smallest key in the symbol table. 
        
         * @return the smallest key in the symbol table 
        
         * @throws nosuchelementexception if the symbol table is empty 
        
         */ 
        
         public 
         key min() { 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "called min() with empty symbol table" 
         ); 
        
         } 
        
         return 
         min(root).key; 
        
         }  
        
         // the smallest key in subtree rooted at x; null if no such key 
        
         private 
         node min(node x) {  
        
         // assert x != null; 
        
         if 
         (x.left ==  
         null 
         ) { 
        
         return 
         x;  
        
         } 
        
         else 
         { 
        
         return 
         min(x.left);  
        
         } 
        
         }  
        
         /** 
        
         * returns the largest key in the symbol table. 
        
         * @return the largest key in the symbol table 
        
         * @throws nosuchelementexception if the symbol table is empty 
        
         */ 
        
         public 
         key max() { 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "called max() with empty symbol table" 
         ); 
        
         } 
        
         return 
         max(root).key; 
        
         }  
        
         // the largest key in the subtree rooted at x; null if no such key 
        
         private 
         node max(node x) {  
        
         // assert x != null; 
        
         if 
         (x.right ==  
         null 
         ) { 
        
         return 
         x;  
        
         } 
        
         else 
         { 
        
         return 
         max(x.right);      
        
         } 
        
         }  
        
         /** 
        
         * returns the largest key in the symbol table less than or equal to key. 
        
         * @param key the key 
        
         * @return the largest key in the symbol table less than or equal to key 
        
         * @throws nosuchelementexception if there is no such key 
        
         * @throws nullpointerexception if key is null 
        
         */ 
        
         public 
         key floor(key key) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "argument to floor() is null" 
         ); 
        
         } 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "called floor() with empty symbol table" 
         ); 
        
         } 
        
         node x = floor(root, key); 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         null 
         ;      
        
         } 
        
         else 
         { 
        
         return 
         x.key; 
        
         } 
        
         }   
        
         // the largest key in the subtree rooted at x less than or equal to the given key 
        
         private 
         node floor(node x, key key) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         null 
         ; 
        
         } 
        
         int 
         cmp = key.compareto(x.key); 
        
         if 
         (cmp ==  
         0 
         ) { 
        
         return 
         x; 
        
         } 
        
         if 
         (cmp <  
         0 
         ) { 
        
         return 
         floor(x.left, key);      
        
         } 
        
         node t = floor(x.right, key); 
        
         if 
         (t !=  
         null 
         ) { 
        
         return 
         t;      
        
         } 
        
         else 
         { 
        
         return 
         x; 
        
         } 
        
         } 
        
         /** 
        
         * returns the smallest key in the symbol table greater than or equal to key. 
        
         * @param key the key 
        
         * @return the smallest key in the symbol table greater than or equal to key 
        
         * @throws nosuchelementexception if there is no such key 
        
         * @throws nullpointerexception if key is null 
        
         */ 
        
         public 
         key ceiling(key key) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "argument to ceiling() is null" 
         ); 
        
         } 
        
         if 
         (isempty()) { 
        
         throw 
         new 
         nosuchelementexception( 
         "called ceiling() with empty symbol table" 
         ); 
        
         } 
        
         node x = ceiling(root, key); 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         null 
         ; 
        
         } 
        
         else 
         { 
        
         return 
         x.key;  
        
         } 
        
         } 
        
         // the smallest key in the subtree rooted at x greater than or equal to the given key 
        
         private 
         node ceiling(node x, key key) {  
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         null 
         ; 
        
         }      
        
         int 
         cmp = key.compareto(x.key); 
        
         if 
         (cmp ==  
         0 
         ) { 
        
         return 
         x; 
        
         } 
        
         if 
         (cmp >  
         0 
         ) { 
        
         return 
         ceiling(x.right, key); 
        
         } 
        
         node t = ceiling(x.left, key); 
        
         if 
         (t !=  
         null 
         ) { 
        
         return 
         t;  
        
         } 
        
         else 
         { 
        
         return 
         x; 
        
         } 
        
         } 
        
         /** 
        
         * return the kth smallest key in the symbol table. 
        
         * @param k the order statistic 
        
         * @return the kth smallest key in the symbol table 
        
         * @throws illegalargumentexception unless k is between 0 and 
        
         *   <em>n</em> − 1 
        
         */ 
        
         public 
         key select( 
         int 
         k) { 
        
         if 
         (k <  
         0 
         || k >= size()) { 
        
         throw 
         new 
         illegalargumentexception(); 
        
         } 
        
         node x = select(root, k); 
        
         return 
         x.key; 
        
         } 
        
         // the key of rank k in the subtree rooted at x 
        
         private 
         node select(node x,  
         int 
         k) { 
        
         // assert x != null; 
        
         // assert k >= 0 && k < size(x); 
        
         int 
         t = size(x.left);  
        
         if   
         (t > k) { 
        
         return 
         select(x.left, k);  
        
         } 
        
         else 
         if 
         (t < k) { 
        
         return 
         select(x.right, k-t- 
         1 
         );  
        
         } 
        
         else 
         { 
        
         return 
         x;  
        
         } 
        
         }  
        
         /** 
        
         * return the number of keys in the symbol table strictly less than key. 
        
         * @param key the key 
        
         * @return the number of keys in the symbol table strictly less than key 
        
         * @throws nullpointerexception if key is null 
        
         */ 
        
         public 
         int 
         rank(key key) { 
        
         if 
         (key ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "argument to rank() is null" 
         ); 
        
         } 
        
         return 
         rank(key, root); 
        
         }  
        
         // number of keys less than key in the subtree rooted at x 
        
         private 
         int 
         rank(key key, node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         0 
         ;  
        
         } 
        
         int 
         cmp = key.compareto(x.key);  
        
         if   
         (cmp <  
         0 
         ) { 
        
         return 
         rank(key, x.left);  
        
         } 
        
         else 
         if 
         (cmp >  
         0 
         ) { 
        
         return 
         1 
         + size(x.left) + rank(key, x.right);  
        
         } 
        
         else 
         { 
        
         return 
         size(x.left);  
        
         } 
        
         }  
        
         /*************************************************************************** 
        
         * range count and range search. 
        
         ***************************************************************************/ 
        
         /** 
        
         * returns all keys in the symbol table as an iterable. 
        
         * to iterate over all of the keys in the symbol table named st, 
        
         * use the foreach notation: for (key key : st.keys()). 
        
         * @return all keys in the symbol table as an iterable 
        
         */ 
        
         public 
         iterable<key> keys() { 
        
         if 
         (isempty()) { 
        
         return 
         new 
         queue<key>(); 
        
         } 
        
         return 
         keys(min(), max()); 
        
         } 
        
         /** 
        
         * returns all keys in the symbol table in the given range, 
        
         * as an iterable. 
        
         * @return all keys in the symbol table between lo  
        
         *  (inclusive) and hi (exclusive) as an iterable 
        
         * @throws nullpointerexception if either lo or hi 
        
         *  is null 
        
         */ 
        
         public 
         iterable<key> keys(key lo, key hi) { 
        
         if 
         (lo ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "first argument to keys() is null" 
         ); 
        
         } 
        
         if 
         (hi ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "second argument to keys() is null" 
         ); 
        
         } 
        
         queue<key> queue =  
         new 
         queue<key>(); 
        
         // if (isempty() || lo.compareto(hi) > 0) return queue; 
        
         keys(root, queue, lo, hi); 
        
         return 
         queue; 
        
         }  
        
         // add the keys between lo and hi in the subtree rooted at x 
        
         // to the queue 
        
         private 
         void 
         keys(node x, queue<key> queue, key lo, key hi) {  
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         ;  
        
         } 
        
         int 
         cmplo = lo.compareto(x.key);  
        
         int 
         cmphi = hi.compareto(x.key);  
        
         if 
         (cmplo <  
         0 
         ) { 
        
         keys(x.left, queue, lo, hi);  
        
         } 
        
         if 
         (cmplo <=  
         0 
         && cmphi >=  
         0 
         ) { 
        
         queue.enqueue(x.key);  
        
         } 
        
         if 
         (cmphi >  
         0 
         ) { 
        
         keys(x.right, queue, lo, hi);  
        
         } 
        
         }  
        
         /** 
        
         * returns the number of keys in the symbol table in the given range. 
        
         * @return the number of keys in the symbol table between lo  
        
         *  (inclusive) and hi (exclusive) 
        
         * @throws nullpointerexception if either lo or hi 
        
         *  is null 
        
         */ 
        
         public 
         int 
         size(key lo, key hi) { 
        
         if 
         (lo ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "first argument to size() is null" 
         ); 
        
         } 
        
         if 
         (hi ==  
         null 
         ) { 
        
         throw 
         new 
         nullpointerexception( 
         "second argument to size() is null" 
         ); 
        
         } 
        
         if 
         (lo.compareto(hi) >  
         0 
         ) { 
        
         return 
         0 
         ; 
        
         } 
        
         if 
         (contains(hi)) { 
        
         return 
         rank(hi) - rank(lo) +  
         1 
         ; 
        
         } 
        
         else 
         { 
        
         return 
         rank(hi) - rank(lo);      
        
         } 
        
         } 
        
         /*************************************************************************** 
        
         * check integrity of red-black tree data structure. 
        
         ***************************************************************************/ 
        
         private 
         boolean 
         check() { 
        
         if 
         (!isbst())      system.out.println( 
         "not in symmetric order" 
         ); 
        
         if 
         (!issizeconsistent()) system.out.println( 
         "subtree counts not consistent" 
         ); 
        
         if 
         (!isrankconsistent()) system.out.println( 
         "ranks not consistent" 
         ); 
        
         if 
         (!is23())       system.out.println( 
         "not a 2-3 tree" 
         ); 
        
         if 
         (!isbalanced())    system.out.println( 
         "not balanced" 
         ); 
        
         return 
         isbst() && issizeconsistent() && isrankconsistent() && is23() && isbalanced(); 
        
         } 
        
         // does this binary tree satisfy symmetric order? 
        
         // note: this test also ensures that data structure is a binary tree since order is strict 
        
         private 
         boolean 
         isbst() { 
        
         return 
         isbst(root,  
         null 
         ,  
         null 
         ); 
        
         } 
        
         // is the tree rooted at x a bst with all keys strictly between min and max 
        
         // (if min or max is null, treat as empty constraint) 
        
         // credit: bob dondero's elegant solution 
        
         private 
         boolean 
         isbst(node x, key min, key max) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         true 
         ; 
        
         } 
        
         if 
         (min !=  
         null 
         && x.key.compareto(min) <=  
         0 
         ) { 
        
         return 
         false 
         ;      
        
         } 
        
         if 
         (max !=  
         null 
         && x.key.compareto(max) >=  
         0 
         ) { 
        
         return 
         false 
         ; 
        
         } 
        
         return 
         isbst(x.left, min, x.key) && isbst(x.right, x.key, max); 
        
         }  
        
         // are the size fields correct? 
        
         private 
         boolean 
         issizeconsistent() {  
        
         return 
         issizeconsistent(root);  
        
         } 
        
         private 
         boolean 
         issizeconsistent(node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         true 
         ; 
        
         } 
        
         if 
         (x.size != size(x.left) + size(x.right) +  
         1 
         ) { 
        
         return 
         false 
         ; 
        
         } 
        
         return 
         issizeconsistent(x.left) && issizeconsistent(x.right); 
        
         }  
        
         // check that ranks are consistent 
        
         private 
         boolean 
         isrankconsistent() { 
        
         for 
         ( 
         int 
         i =  
         0 
         ; i < size(); i++) { 
        
         if 
         (i != rank(select(i))) { 
        
         return 
         false 
         ; 
        
         } 
        
         } 
        
         for 
         (key key : keys()) { 
        
         if 
         (key.compareto(select(rank(key))) !=  
         0 
         ) { 
        
         return 
         false 
         ; 
        
         } 
        
         } 
        
         return 
         true 
         ; 
        
         } 
        
         // does the tree have no red right links, and at most one (left) 
        
         // red links in a row on any path? 
        
         private 
         boolean 
         is23() {  
        
         return 
         is23(root);  
        
         } 
        
         private 
         boolean 
         is23(node x) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         true 
         ; 
        
         } 
        
         if 
         (isred(x.right)) { 
        
         return 
         false 
         ; 
        
         } 
        
         if 
         (x != root && isred(x) && isred(x.left)){ 
        
         return 
         false 
         ; 
        
         } 
        
         return 
         is23(x.left) && is23(x.right); 
        
         }  
        
         // do all paths from root to leaf have same number of black edges? 
        
         private 
         boolean 
         isbalanced() {  
        
         int 
         black =  
         0 
         ;    
         // number of black links on path from root to min 
        
         node x = root; 
        
         while 
         (x !=  
         null 
         ) { 
        
         if 
         (!isred(x)) black++; 
        
         x = x.left; 
        
         } 
        
         return 
         isbalanced(root, black); 
        
         } 
        
         // does every path from the root to a leaf have the given number of black links? 
        
         private 
         boolean 
         isbalanced(node x,  
         int 
         black) { 
        
         if 
         (x ==  
         null 
         ) { 
        
         return 
         black ==  
         0 
         ;      
        
         } 
        
         if 
         (!isred(x)) { 
        
         black--; 
        
         } 
        
         return 
         isbalanced(x.left, black) && isbalanced(x.right, black); 
        
         }  
        
         /** 
        
         * unit tests the redblackbst data type. 
        
         */ 
        
         public 
         static 
         void 
         main(string[] args) {  
        
         redblackbst<string, integer= 
         "" 
         > st =  
         new 
         redblackbst<string, integer= 
         "" 
         >(); 
        
         string data =  
         "a b c d e f g h m n o p" 
         ; 
        
         scanner sc =  
         new 
         scanner(data); 
        
         int 
         i =  
         0 
         ; 
        
         while 
         (sc.hasnext()) {      
        
         string key = sc.next(); 
        
         st.put(key, i); 
        
         i++; 
        
         } 
        
         sc.close();    
        
         for 
         (string s : st.keys()) 
        
         system.out.println(s +  
         " " 
         + st.get(s)); 
        
         system.out.println(); 
        
         boolean 
         result = st.check(); 
        
         system.out.println( 
         "check: " 
         + result); 
        
         } 
        
         }

输出:

总结。

以上就是本文关于java算法实现红黑树完整代码示例的全部内容，希望对大家有所帮助。有什么问题可以随时留言，小编会及时回复大家的。感谢朋友们对本站的支持！。

原文链接：https://www.2cto.com/kf/201608/541726.html 。

最后此篇关于java算法实现红黑树完整代码示例的文章就讲到这里了,如果你想了解更多关于java算法实现红黑树完整代码示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐：江南百景图百年银杏放哪江南百景图百年银杏位置介绍

文章推荐：适合女生简单的英文网名带翻译英文网名全新很有内涵简短2021

文章推荐：明日方舟霜冻废墟8打法明日方舟霜冻废墟8攻略

文章推荐： 2021独一无二的扎心网名伤感很热门的丧系伤感网名

c - MPI_Allreduce 未按预期工作 - 红黑 SOR
我正在实现红黑 SOR 的并行版本。我想获得每个进程的最大误差的 MPI_Allreduce 部分不起作用。它永远不会改变，即使只有一个过程，它也会给出高于 2.0 的值。怎么回事？？这是代码，有
gpu - OpenACC 红黑 Gauss-Seidel 比 CPU 慢
我为拉普拉斯方程(一个简单的加热板问题)在我的红黑 Gauss-Seidel 求解器中添加了 OpenACC 指令，但是 GPU 加速的代码并不比 CPU 快，即使对于大问题也是如此。我还编写了一个

qq735679552

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

java算法实现红黑树完整代码示例