基于Java继承实现红黑树的泛型二叉搜索树设计冲突问题

云原生阿岚

2026-5-25

用Java继承从基础BST扩展红黑树的实现思路

嘿，我明白你的困惑点——基础二叉搜索树（BST）的节点是泛型类，而红黑树需要带颜色属性的节点，同时还要复用BST的核心逻辑，这确实容易在继承设计上卡壳。下面我给你梳理一套清晰的实现思路，完全基于Java继承来落地：

第一步：重构基础BST，让它具备可扩展性

首先得把你的基础BST调整成适合被继承的结构，核心是让Node类和核心操作逻辑对开放子类访问：

public class BinarySearchTree<K extends Comparable<K>, V> {
    // 把Node设为protected静态内部类，允许子类继承扩展
    protected static class Node<K, V> {
        K key;
        V value;
        Node<K, V> left;
        Node<K, V> right;
        Node<K, V> parent; // 一定要加父节点引用，红黑树旋转、调整必用

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            this.parent = null;
        }
    }

    protected Node<K, V> root;

    // 对外暴露的add方法，内部调用可被重写的递归插入逻辑
    public void add(K key, V value) {
        root = insertRecursive(root, key, value, null);
    }

    // 把插入核心逻辑抽成protected方法，方便子类重写
    protected Node<K, V> insertRecursive(Node<K, V> current, K key, V value, Node<K, V> parent) {
        if (current == null) {
            Node<K, V> newNode = new Node<>(key, value);
            newNode.parent = parent;
            return newNode;
        }

        int cmp = key.compareTo(current.key);
        if (cmp < 0) {
            current.left = insertRecursive(current.left, key, value, current);
        } else if (cmp > 0) {
            current.right = insertRecursive(current.right, key, value, current);
        } else {
            // 键已存在时更新值
            current.value = value;
        }
        return current;
    }

    // 同理，把find、delete的核心逻辑也抽成protected方法，方便子类复用或重写
    public V find(K key) {
        return findRecursive(root, key);
    }

    protected V findRecursive(Node<K, V> current, K key) {
        if (current == null) return null;
        int cmp = key.compareTo(current.key);
        if (cmp == 0) return current.value;
        return cmp < 0 ? findRecursive(current.left, key) : findRecursive(current.right, key);
    }
}

第二步：定义红黑树的节点类，继承基础Node

红黑树的节点需要额外的颜色属性，我们在红黑树类里定义自己的RBNode，直接继承基础BST的Node：

public class RedBlackTree<K extends Comparable<K>, V> extends BinarySearchTree<K, V> {
    // 红黑树节点，继承基础Node并添加颜色属性
    protected static class RBNode<K, V> extends Node<K, V> {
        enum Color { RED, BLACK }
        Color color;

        public RBNode(K key, V value) {
            super(key, value);
            this.color = Color.RED; // 新插入节点默认红色，符合红黑树规则
        }
    }

    // 重写root属性，直接指定为RBNode类型，避免后续频繁强转
    @SuppressWarnings("unchecked")
    @Override
    protected RBNode<K, V> root;

    public RedBlackTree() {
        this.root = null;
    }
}

这里用@SuppressWarnings压制泛型转换警告是安全的——因为红黑树里所有节点都是RBNode，不会出现类型不匹配的情况。

第三步：重写BST操作，添加红黑树平衡维护

红黑树的核心是在BST的插入/删除操作完成后，通过旋转+颜色调整维护红黑树的5条性质。我们重写父类的插入方法，在BST插入逻辑后添加平衡修复：

@Override
public void add(K key, V value) {
    // 调用重写后的递归插入方法，直接得到RBNode
    RBNode<K, V> newNode = insertRecursive(root, key, value, null);
    // 根节点必须是黑色
    if (newNode == root) {
        newNode.color = RBNode.Color.BLACK;
        return;
    }
    // 修复红黑树性质
    fixInsertion(newNode);
}

// 重写父类的insertRecursive，返回RBNode类型
@Override
protected RBNode<K, V> insertRecursive(Node<K, V> current, K key, V value, Node<K, V> parent) {
    if (current == null) {
        RBNode<K, V> newNode = new RBNode<>(key, value);
        newNode.parent = parent;
        return newNode;
    }

    int cmp = key.compareTo(current.key);
    if (cmp < 0) {
        current.left = insertRecursive(current.left, key, value, current);
    } else if (cmp > 0) {
        current.right = insertRecursive(current.right, key, value, current);
    } else {
        // 更新已有键的值，返回当前节点的RBNode类型
        current.value = value;
        return (RBNode<K, V>) current;
    }
    return (RBNode<K, V>) current;
}

// 插入后的红黑树平衡修复逻辑
private void fixInsertion(RBNode<K, V> node) {
    RBNode<K, V> parent;
    RBNode<K, V> grandParent;

    while (node != root && ((RBNode<K, V>) node.parent).color == RBNode.Color.RED) {
        parent = (RBNode<K, V>) node.parent;
        grandParent = (RBNode<K, V>) parent.parent;

        // 父节点是祖父节点的左孩子的情况
        if (parent == grandParent.left) {
            RBNode<K, V> uncle = (RBNode<K, V>) grandParent.right;

            // 子情况1：叔节点是红色，只需调整颜色
            if (uncle != null && uncle.color == RBNode.Color.RED) {
                grandParent.color = RBNode.Color.RED;
                parent.color = RBNode.Color.BLACK;
                uncle.color = RBNode.Color.BLACK;
                node = grandParent;
            } else {
                // 子情况2：当前节点是父节点的右孩子，先左旋父节点
                if (node == parent.right) {
                    leftRotate(parent);
                    node = parent;
                    parent = (RBNode<K, V>) node.parent;
                }
                // 子情况3：当前节点是父节点的左孩子，右旋祖父节点+调整颜色
                rightRotate(grandParent);
                RBNode.Color temp = parent.color;
                parent.color = grandParent.color;
                grandParent.color = temp;
                node = parent;
            }
        } else {
            // 父节点是祖父节点的右孩子，和左孩子情况对称
            RBNode<K, V> uncle = (RBNode<K, V>) grandParent.left;

            if (uncle != null && uncle.color == RBNode.Color.RED) {
                grandParent.color = RBNode.Color.RED;
                parent.color = RBNode.Color.BLACK;
                uncle.color = RBNode.Color.BLACK;
                node = grandParent;
            } else {
                if (node == parent.left) {
                    rightRotate(parent);
                    node = parent;
                    parent = (RBNode<K, V>) node.parent;
                }
                leftRotate(grandParent);
                RBNode.Color temp = parent.color;
                parent.color = grandParent.color;
                grandParent.color = temp;
                node = parent;
            }
        }
    }
    // 确保根节点始终为黑色
    root.color = RBNode.Color.BLACK;
}

// 左旋操作实现
private void leftRotate(RBNode<K, V> node) {
    RBNode<K, V> rightChild = (RBNode<K, V>) node.right;
    node.right = rightChild.left;

    if (rightChild.left != null) {
        rightChild.left.parent = node;
    }

    rightChild.parent = node.parent;

    if (node.parent == null) {
        root = rightChild;
    } else if (node == node.parent.left) {
        node.parent.left = rightChild;
    } else {
        node.parent.right = rightChild;
    }

    rightChild.left = node;
    node.parent = rightChild;
}

// 右旋操作实现，和左旋对称
private void rightRotate(RBNode<K, V> node) {
    RBNode<K, V> leftChild = (RBNode<K, V>) node.left;
    node.left = leftChild.right;

    if (leftChild.right != null) {
        leftChild.right.parent = node;
    }

    leftChild.parent = node.parent;

    if (node.parent == null) {
        root = leftChild;
    } else if (node == node.parent.right) {
        node.parent.right = leftChild;
    } else {
        node.parent.left = leftChild;
    }

    leftChild.right = node;
    node.parent = leftChild;
}

第四步：删除操作的继承思路

删除操作的逻辑比插入更复杂，但核心思路一致：

重写父类的delete相关方法，执行BST的删除逻辑
找到被删除节点（或替代它的后继节点）
修复红黑树的双重黑色节点问题，维护红黑树性质

你可以参考插入的模式，把父类的删除核心逻辑抽成protected方法，然后在红黑树类里重写，添加修复逻辑。

核心注意点

父类方法的可扩展性：父类的核心操作一定要抽成protected，让子类可以重写而不是完全重写整个方法
避免冗余强转：通过重写root为RBNode类型，以及在子类重写递归方法时直接返回RBNode，减少不必要的类型转换
泛型兼容性：红黑树的泛型约束要和父类保持一致（K extends Comparable<K>），确保键的比较逻辑复用

内容的提问来源于stack exchange，提问作者Juan David

基于Java继承实现红黑树的泛型二叉搜索树设计冲突问题

第一步：重构基础BST，让它具备可扩展性 #

第二步：定义红黑树的节点类，继承基础Node #

第三步：重写BST操作，添加红黑树平衡维护 #

第四步：删除操作的继承思路 #

核心注意点 #

第一步：重构基础BST，让它具备可扩展性

第二步：定义红黑树的节点类，继承基础Node

第三步：重写BST操作，添加红黑树平衡维护

第四步：删除操作的继承思路

核心注意点