本文共 17838 字，大约阅读时间需要 59 分钟。

红黑树

红黑树是一种自平衡的二叉搜索树

1.性质

1. 节点是RED 或者BLACK

2. 根节点是BLACK

3. 叶子节点（外部节点，空节点）都是BLACK

4. RED 节点的子节点都是BLACK

   • RED 节点的parent 都是BLACK

   • 从根节点到叶子节点的所有路径上不能有2 个连续的RED 节点

5. 从任一节点到叶子节点的所有路径都包含相同数目的BLACK 节点

2.红黑树的等价变换

• 红黑树与4阶B树具有等价性
• BLACK 节点与它的RED子节点融合在一起，形成1个B树节点
• 红黑树的BLACK 节点个数与4阶B树的节点总个数相等

】

3.功能实现

1. 添加

• 4阶B树所有节点的元素个数x 都符合1 ≤ x≤ 3

• 建议新添加的节点默认为RED，这样能够让红黑树的性质尽快满足（性质1、2、3、5 都满足，性质4 不一定）

1. 如果添加的是根节点，染成BLACK 即可

2. 如果parent为BLACK

   • 不用处理

3. 如果parent为RED

   1. 判定条件：uncle不是RED

      1. parent 染成BLACK，grand 染成RED

      2. grand 进行单旋操作
      • LL：右旋转

      • RR：左旋转

   2. 判定条件：uncle不是RED

      1. 自己染成BLACK，grand 染成RED  2. 进行双旋操作  - LR：parent 左旋转，grand 右旋转  - RL：parent 右旋转，grand 左旋转
   3. 判定条件：uncle不是RED

      1. parent、uncle 染成BLACK

      2. grand 向上合并
      • 染成RED，当做是新添加的节点进行处理

        [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-6qyLHw5I-1615991202619)(C:\Users\15463\AppData\Roaming\Typora\typora-user-images\image-20210317214804581.png)]

4. 代码

   protected void afterAdd(Node
        
          node) {
        		Node
         
           parent = node.parent;				// 添加的是根节点 或者 上溢到达了根节点		if (parent == null) {
        			black(node);			return;		}				// 如果父节点是黑色，直接返回		if (isBlack(parent)) return;				// 叔父节点		Node
          
            uncle = parent.sibling();		// 祖父节点		Node
           
             grand = red(parent.parent);		if (isRed(uncle)) {
         // 叔父节点是红色【B树节点上溢】			black(parent);			black(uncle);			// 把祖父节点当做是新添加的节点			afterAdd(grand);			return;		}				// 叔父节点不是红色		if (parent.isLeftChild()) {
         // L			if (node.isLeftChild()) {
         // LL				black(parent);			} else {
         // LR				black(node);				rotateLeft(parent);			}			rotateRight(grand);		} else {
         // R			if (node.isLeftChild()) {
         // RL				black(node);				rotateRight(parent);			} else {
         // RR				black(parent);			}			rotateLeft(grand);		}	}
           
          
         
        

2.删除

B树中，最后真正删除的都在叶子节点上。

1. 删除的是RED结点

   直接删除

2. 删除BLACKE结点

   1. 有两个RED结点的BLACK结点
      • 不可能被直接删除，因为会找它的子节点替代删除
   2. 有一个RED结点的BLACK结点
   3. BLACK结点

• 删除拥有一个RED节点的BLACK结点

  1. 判定条件：用以替代的是RED

  2. 将替代的子节点染成BLACK

• 删除BLACK子节点（sibling（兄弟）为BLACK）

  • BLACK 叶子节点被删除后，会导致B树节点下溢（比如删除88）

  • 判定条件：sibling 至少有1 个RED 子节点

  • 进行旋转操作

  • 旋转之后的中心节点继承parent 的颜色

  • 旋转之后的左右节点染为BLACK

• 删除BLACK子节点（sibling（兄弟）为BLACK）

  • 判定条件：sibling 没有1 个RED 子节点

  • 将sibling 染成RED、parent 染成BLACK 即可修复红黑树性质

  • 如果parent 是BLACK

  • 会导致parent 也下溢

  • 这时只需要把parent 当做被删除的节点处理即可

• 删除BLACK子节点（sibling（兄弟）为RED）

  • 如果sibling 是RED

  • sibling 染成BLACK，parent 染成RED，进行旋转

  • 于是又回到sibling 是BLACK 的情况

• 代码

  protected void afterRemove(Node
       
         node) {
       		// 如果删除的节点是红色		// 或者 用以取代删除节点的子节点是红色		if (isRed(node)) {
       			black(node);			return;		}				Node
        
          parent = node.parent;		// 删除的是根节点		if (parent == null) return;				// 删除的是黑色叶子节点【下溢】		// 判断被删除的node是左还是右		boolean left = parent.left == null || node.isLeftChild();		Node
         
           sibling = left ? parent.right : parent.left;		if (left) {
        // 被删除的节点在左边，兄弟节点在右边			if (isRed(sibling)) {
        // 兄弟节点是红色				black(sibling);				red(parent);				rotateLeft(parent);				// 更换兄弟				sibling = parent.right;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {
       				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {
       					afterRemove(parent);				}			} else {
        // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.right)) {
       					rotateRight(sibling);					sibling = parent.right;				}								color(sibling, colorOf(parent));				black(sibling.right);				black(parent);				rotateLeft(parent);			}		} else {
        // 被删除的节点在右边，兄弟节点在左边			if (isRed(sibling)) {
        // 兄弟节点是红色				black(sibling);				red(parent);				rotateRight(parent);				// 更换兄弟				sibling = parent.left;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {
       				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {
       					afterRemove(parent);				}			} else {
        // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.left)) {
       					rotateLeft(sibling);					sibling = parent.left;				}								color(sibling, colorOf(parent));				black(sibling.left);				black(parent);				rotateRight(parent);			}		}	}
         
        
       

4.红黑树的平衡

• 那5条性质可以保证红黑树等价于4阶B树
• 相比于AVL树，红黑树的平衡标准：没有一条路径会大于其它路径的2倍
• 是一种弱平衡，黑高度平衡
• 红黑树的最大高度是$2\ast lo{g}_{2}n+1$,依然是O（logn）级别

5.平均时间复杂度

• 搜索O(logn)
• 添加O(logn)，O（1）次旋转
• 删除O(logn)，O（1）次旋转

6.AVL树与红黑树

• AVL树

1. 平衡标准比较严格：每个左右子树的高度差不超过1

2. 最大高度是$1.44\ast lo{g}_{2}n+1-1.328$（100W个节点，AVL树最大树高28）

3. 搜索、添加、删除都是O(logn) 复杂度，其中添加仅需O(1) 次旋转调整、删除最多需要O(logn) 次旋转调整

• 红黑树

1. 平衡标准比较宽松：没有一条路径会大于其他路径的2倍

2. 最大高度是$2\ast lo{g}_{2}n+1$（100W个节点，红黑树最大树高40）

3. 搜索、添加、删除都是O(logn) 复杂度，其中添加、删除都仅需O(1) 次旋转调整

• 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树

• 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

• 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

7. 全部代码

1. 红黑树

import java.util.Comparator;public class RBTree
   
     extends BBST
    
      {
   	private static final boolean RED = false;	private static final boolean BLACK = true;		public RBTree() {
   		this(null);	}		public RBTree(Comparator
     
       comparator) {
   		super(comparator);	}		@Override	protected void afterAdd(Node
      
        node) {
   		Node
       
         parent = node.parent;				// 添加的是根节点 或者 上溢到达了根节点		if (parent == null) {
   			black(node);			return;		}				// 如果父节点是黑色，直接返回		if (isBlack(parent)) return;				// 叔父节点		Node
        
          uncle = parent.sibling(); // 祖父节点 Node
         
           grand = red(parent.parent); if (isRed(uncle)) { // 叔父节点是红色【B树节点上溢】 black(parent); black(uncle); // 把祖父节点当做是新添加的节点 afterAdd(grand); return; } // 叔父节点不是红色 if (parent.isLeftChild()) { // L if (node.isLeftChild()) { // LL black(parent); } else { // LR black(node); rotateLeft(parent); } rotateRight(grand); } else { // R if (node.isLeftChild()) { // RL black(node); rotateRight(parent); } else { // RR black(parent); } rotateLeft(grand); } } @Override protected void afterRemove(Node
          
            node) { // 如果删除的节点是红色 // 或者 用以取代删除节点的子节点是红色 if (isRed(node)) { black(node); return; } Node
           
             parent = node.parent; // 删除的是根节点 if (parent == null) return; // 删除的是黑色叶子节点【下溢】 // 判断被删除的node是左还是右 boolean left = parent.left == null || node.isLeftChild(); Node
            
              sibling = left ? parent.right : parent.left; if (left) { // 被删除的节点在左边，兄弟节点在右边 if (isRed(sibling)) { // 兄弟节点是红色 black(sibling); red(parent); rotateLeft(parent); // 更换兄弟 sibling = parent.right; } // 兄弟节点必然是黑色 if (isBlack(sibling.left) && isBlack(sibling.right)) { // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) { afterRemove(parent); } } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素 // 兄弟节点的左边是黑色，兄弟要先旋转 if (isBlack(sibling.right)) { rotateRight(sibling); sibling = parent.right; } color(sibling, colorOf(parent)); black(sibling.right); black(parent); rotateLeft(parent); } } else { // 被删除的节点在右边，兄弟节点在左边 if (isRed(sibling)) { // 兄弟节点是红色 black(sibling); red(parent); rotateRight(parent); // 更换兄弟 sibling = parent.left; } // 兄弟节点必然是黑色 if (isBlack(sibling.left) && isBlack(sibling.right)) { // 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并 boolean parentBlack = isBlack(parent); black(parent); red(sibling); if (parentBlack) { afterRemove(parent); } } else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素 // 兄弟节点的左边是黑色，兄弟要先旋转 if (isBlack(sibling.left)) { rotateLeft(sibling); sibling = parent.left; } color(sibling, colorOf(parent)); black(sibling.left); black(parent); rotateRight(parent); } } } private Node
             
               color(Node
              
                node, boolean color) { if (node == null) return node; ((RBNode
               
                )node).color = color; return node; } private Node
                
                  red(Node
                 
                   node) { return color(node, RED); } private Node
                  
                    black(Node
                   
                     node) { return color(node, BLACK); } private boolean colorOf(Node
                    
                      node) { return node == null ? BLACK : ((RBNode
                     
                      )node).color; } private boolean isBlack(Node
                      
                        node) { return colorOf(node) == BLACK; } private boolean isRed(Node
                       
                         node) { return colorOf(node) == RED; } @Override protected Node
                        
                          createNode(E element, Node
                         
                           parent) { return new RBNode<>(element, parent); } private static class RBNode
                          
                            extends Node
                           
                             { boolean color = RED; public RBNode(E element, Node
                            
                              parent) { super(element, parent); } @Override public String toString() { String str = ""; if (color == RED) { str = "R_"; } return str + element.toString(); } }}
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

2. BBST

   import java.util.Comparator;public class BBST
        
          extends BST
         
           {	public BBST() {		this(null);	}		public BBST(Comparator
          
            comparator) {		super(comparator);	}	protected void rotateLeft(Node
           
             grand) {		Node
            
              parent = grand.right;		Node
             
               child = parent.left; grand.right = child; parent.left = grand; afterRotate(grand, parent, child); } protected void rotateRight(Node
              
                grand) { Node
               
                 parent = grand.left; Node
                
                  child = parent.right; grand.left = child; parent.right = grand; afterRotate(grand, parent, child); } protected void afterRotate(Node
                 
                   grand, Node
                  
                    parent, Node
                   
                     child) { // 让parent称为子树的根节点 parent.parent = grand.parent; if (grand.isLeftChild()) { grand.parent.left = parent; } else if (grand.isRightChild()) { grand.parent.right = parent; } else { // grand是root节点 root = parent; } // 更新child的parent if (child != null) { child.parent = grand; } // 更新grand的parent grand.parent = parent; } protected void rotate( Node
                    
                      r, // 子树的根节点 Node
                     
                       b, Node
                      
                        c, Node
                       
                         d, Node
                        
                          e, Node
                         
                           f) { // 让d成为这棵子树的根节点 d.parent = r.parent; if (r.isLeftChild()) { r.parent.left = d; } else if (r.isRightChild()) { r.parent.right = d; } else { root = d; } //b-c b.right = c; if (c != null) { c.parent = b; } // e-f f.left = e; if (e != null) { e.parent = f; } // b-d-f d.left = b; d.right = f; b.parent = d; f.parent = d; }}
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        

3. BST

   package com.mj.tree;import java.util.Comparator;@SuppressWarnings("unchecked")public class BST
        
          extends BinaryTree
         
           {	private Comparator
          
            comparator;		public BST() {		this(null);	}		public BST(Comparator
           
             comparator) {		this.comparator = comparator;	}	public void add(E element) {		elementNotNullCheck(element);				// 添加第一个节点		if (root == null) {			root = createNode(element, null);			size++;			// 新添加节点之后的处理			afterAdd(root);			return;		}				// 添加的不是第一个节点		// 找到父节点		Node
            
              parent = root;		Node
             
               node = root; int cmp = 0; do { cmp = compare(element, node.element); parent = node; if (cmp > 0) { node = node.right; } else if (cmp < 0) { node = node.left; } else { // 相等 node.element = element; return; } } while (node != null); // 看看插入到父节点的哪个位置 Node
              
                newNode = createNode(element, parent); if (cmp > 0) { parent.right = newNode; } else { parent.left = newNode; } size++; // 新添加节点之后的处理 afterAdd(newNode); } /** * 添加node之后的调整 * @param node 新添加的节点 */ protected void afterAdd(Node
               
                 node) { } /** * 删除node之后的调整 * @param node 被删除的节点 或者 用以取代被删除节点的子节点（当被删除节点的度为1） */ protected void afterRemove(Node
                
                  node) { } public void remove(E element) { remove(node(element)); } public boolean contains(E element) { return node(element) != null; } private void remove(Node
                 
                   node) { if (node == null) return; size--; if (node.hasTwoChildren()) { // 度为2的节点 // 找到后继节点 Node
                  
                    s = successor(node); // 用后继节点的值覆盖度为2的节点的值 node.element = s.element; // 删除后继节点 node = s; } // 删除node节点（node的度必然是1或者0） Node
                   
                     replacement = node.left != null ? node.left : node.right; if (replacement != null) { // node是度为1的节点 // 更改parent replacement.parent = node.parent; // 更改parent的left、right的指向 if (node.parent == null) { // node是度为1的节点并且是根节点 root = replacement; } else if (node == node.parent.left) { node.parent.left = replacement; } else { // node == node.parent.right node.parent.right = replacement; } // 删除节点之后的处理 afterRemove(replacement); } else if (node.parent == null) { // node是叶子节点并且是根节点 root = null; // 删除节点之后的处理 afterRemove(node); } else { // node是叶子节点，但不是根节点 if (node == node.parent.left) { node.parent.left = null; } else { // node == node.parent.right node.parent.right = null; } // 删除节点之后的处理 afterRemove(node); } } private Node
                    
                      node(E element) { Node
                     
                       node = root; while (node != null) { int cmp = compare(element, node.element); if (cmp == 0) return node; if (cmp > 0) { node = node.right; } else { // cmp < 0 node = node.left; } } return null; } /** * @return 返回值等于0，代表e1和e2相等；返回值大于0，代表e1大于e2；返回值小于于0，代表e1小于e2 */ private int compare(E e1, E e2) { if (comparator != null) { return comparator.compare(e1, e2); } return ((Comparable
                      
                       )e1).compareTo(e2); } private void elementNotNullCheck(E element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } }}
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        

4. BinaryTree

   package com.mj.tree;import java.util.LinkedList;import java.util.Queue;import com.mj.printer.BinaryTreeInfo;//BinaryTreeInfo删除@SuppressWarnings("unchecked")public class BinaryTree
        
          implements BinaryTreeInfo {
        	protected int size;	protected Node
         
           root;		public int size() {
        		return size;	}	public boolean isEmpty() {
        		return size == 0;	}	public void clear() {
        		root = null;		size = 0;	}		public void preorder(Visitor
          
            visitor) {
        		if (visitor == null) return;		preorder(root, visitor);	}		private void preorder(Node
           
             node, Visitor
            
              visitor) {
        		if (node == null || visitor.stop) return;				visitor.stop = visitor.visit(node.element);		preorder(node.left, visitor);		preorder(node.right, visitor);	}		public void inorder(Visitor
             
               visitor) { if (visitor == null) return; inorder(root, visitor); } private void inorder(Node
              
                node, Visitor
               
                 visitor) { if (node == null || visitor.stop) return; inorder(node.left, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); inorder(node.right, visitor); } public void postorder(Visitor
                
                  visitor) { if (visitor == null) return; postorder(root, visitor); } private void postorder(Node
                 
                   node, Visitor
                  
                    visitor) { if (node == null || visitor.stop) return; postorder(node.left, visitor); postorder(node.right, visitor); if (visitor.stop) return; visitor.stop = visitor.visit(node.element); } public void levelOrder(Visitor
                   
                     visitor) { if (root == null || visitor == null) return; Queue
                    
                     
                      > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node
                      
                        node = queue.poll(); if (visitor.visit(node.element)) return; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } } public boolean isComplete() { if (root == null) return false; Queue
                       
                        
                         > queue = new LinkedList<>(); queue.offer(root); boolean leaf = false; while (!queue.isEmpty()) { Node
                         
                           node = queue.poll(); if (leaf && !node.isLeaf()) return false; if (node.left != null) { queue.offer(node.left); } else if (node.right != null) { return false; } if (node.right != null) { queue.offer(node.right); } else { // 后面遍历的节点都必须是叶子节点 leaf = true; } } return true; } public int height() { if (root == null) return 0; // 树的高度 int height = 0; // 存储着每一层的元素数量 int levelSize = 1; Queue
                          
                           
                            > queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { Node
                            
                              node = queue.poll(); levelSize--; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } if (levelSize == 0) { // 意味着即将要访问下一层 levelSize = queue.size(); height++; } } return height; } public int height2() { return height(root); } private int height(Node
                             
                               node) { if (node == null) return 0; return 1 + Math.max(height(node.left), height(node.right)); } protected Node
                              
                                createNode(E element, Node
                               
                                 parent) { return new Node<>(element, parent); } protected Node
                                
                                  predecessor(Node
                                 
                                   node) { if (node == null) return null; // 前驱节点在左子树当中（left.right.right.right....） Node
                                  
                                    p = node.left; if (p != null) { while (p.right != null) { p = p.right; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.left) { node = node.parent; } // node.parent == null // node == node.parent.right return node.parent; } protected Node
                                   
                                     successor(Node
                                    
                                      node) { if (node == null) return null; // 前驱节点在左子树当中（right.left.left.left....） Node
                                     
                                       p = node.right; if (p != null) { while (p.left != null) { p = p.left; } return p; } // 从父节点、祖父节点中寻找前驱节点 while (node.parent != null && node == node.parent.right) { node = node.parent; } return node.parent; } public static abstract class Visitor
                                      
                                        { boolean stop; /** * @return 如果返回true，就代表停止遍历 */ abstract boolean visit(E element); } protected static class Node
                                       
                                         { E element; Node
                                        
                                          left; Node
                                         
                                           right; Node
                                          
                                            parent; public Node(E element, Node
                                           
                                             parent) { this.element = element; this.parent = parent; } public boolean isLeaf() { return left == null && right == null; } public boolean hasTwoChildren() { return left != null && right != null; } public boolean isLeftChild() { return parent != null && this == parent.left; } public boolean isRightChild() { return parent != null && this == parent.right; } public Node
                                            
                                              sibling() { if (isLeftChild()) { return parent.right; } if (isRightChild()) { return parent.left; } return null; } } @Override public Object root() { return root; } @Override public Object left(Object node) { return ((Node
                                             
                                              )node).left; } @Override public Object right(Object node) { return ((Node
                                              
                                               )node).right; } @Override public Object string(Object node) { return node; }}
                                              
                                             
                                            
                                           
                                          
                                         
                                        
                                       
                                      
                                     
                                    
                                   
                                  
                                 
                                
                               
                              
                             
                            
                           
                          
                         
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        

nt = parent;

public boolean isLeaf() {		return left == null && right == null;	}		public boolean hasTwoChildren() {		return left != null && right != null;	}		public boolean isLeftChild() {		return parent != null && this == parent.left;	}		public boolean isRightChild() {		return parent != null && this == parent.right;	}		public Node
   
     sibling() {		if (isLeftChild()) {			return parent.right;		}				if (isRightChild()) {			return parent.left;		}				return null;	}}@Overridepublic Object root() {	return root;}@Overridepublic Object left(Object node) {	return ((Node
    
     )node).left;}@Overridepublic Object right(Object node) {	return ((Node
     
      )node).right;}@Overridepublic Object string(Object node) {	return node;}
     
    
   

}

转载地址：http://winwi.baihongyu.com/