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

红黑树（Red-Black Tree）是一种高效的平衡二叉搜索树，它通过在每个节点上记录颜色信息（Red或Black）来保证树的平衡性。与AVL树和其他平衡树不同，红黑树的平衡性是相对的，而不是绝对的。红黑树的主要特点是：最长路径的长度不会超过最短路径的两倍，这使得它在实际应用中表现优异。

红黑树的性质

这些性质保证了红黑树在插入、删除和查找操作时的平衡性。

红黑树的查找

红黑树的查找过程与普通二叉搜索树相同。由于红黑树的平衡性保证，查找的平均时间复杂度是O(log N)。

红黑树的插入

红黑树的插入过程分为两个主要步骤：

插入过程分为以下几种情况：

AVL树与红黑树的比较

红黑树和AVL树都是高效的平衡二叉搜索树，但它们的实现方式和平衡机制有所不同：

• 红黑树的插入和旋转次数较少，实现简单且性能优异。
• AVL树的查找性能略优，但插入和删除操作的复杂度较高。

TreeMap的源码示例

TreeMap的实现通常基于红黑树。以下是红黑树插入和调整的一些关键代码片段：

public V put(K key, V value) {
    Entry
   
     t = root;
    if (t == null) {
        root = new Entry<>(key, value, null);
        size = 1;
        modCount++;
        return null;
    }
    int cmp;
    Comparator
    
      cpr = comparator;
    if (cpr != null) {
        while (t != null) {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0) t = t.left;
            else if (cmp > 0) t = t.right;
            else return t.setValue(value);
        }
    } else {
        Comparable
     
       k = (Comparable
      
       ) key;
        while (t != null) {
            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);
        }
    }
    Entry
       
         e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e;
    else parent.right = e;
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}
private void fixAfterInsertion(Entry
        
          x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { Entry
         
           p = x.parent; Entry
          
            pp = p.parent; boolean isLeftChild = (p == p.left); Entry
           
             y = isLeftChild ? p.right : p.left; if (y != null && y.color == RED) { p.color = BLACK; y.color = BLACK; pp.color = RED; x = pp; } else { if (isLeftChild) { x = p; rotateLeft(p); } else { x = p; rotateRight(p); } p.color = BLACK; pp.color = RED; } } root.color = BLACK; }
           
          
         
        
       
      
     
    
   

总结

红黑树通过简单的颜色规则和插入调整机制，实现了高效的平衡二叉搜索树。它在实际应用中的表现优于AVL树，且实现复杂度较低，因此在Java的标准库（如TreeMap和TreeSet）中被广泛使用。