时间戳

首页 > 解决方案 > 将二叉搜索树扩展到红黑树

java - 将二叉搜索树扩展到红黑树

问题描述

我已经实现了一个简单的二叉搜索树。我想创建一个子类红黑树，但我遇到了问题。BST 的代码如下，去掉了不相关的细节。BST 工作得非常好。

节点：

public Node {
    private int key;

    public Node left;
    public Node right;
    public Node parent;

    public Node(int key){
        // init
    }
}

英国夏令时：

public BinarySearchTree {
    protected Node root;

    public void insert(int key){
        Node insertNode = new Node(key); // This is problematic
        // perform insertion
    }
}

我需要子类Node来添加颜色属性：

Rbt节点：

public RbtNode extends Node {
    private boolean isBlack;

    public RbtNode(int key){
        // init
    }
}

和RedBlackTree班级

红黑树

public RedBlackTree {

    public void insert(int key){
        super.insert(key);
        // perform RBT fixes
    }
}

如您所见，我想重用 of 的insert方法BinarySearchTree，但是由于它插入的是 aNode而不是 a RbtNode，所以它不起作用。

我想出的一个解决方案是创建一个createNode(int key)可以覆盖的单独方法，但是在访问/操作子类上的节点时我需要做很多类型转换。

有没有更清洁的解决方案，最好是没有类型转换的解决方案？

编辑：super.insert问题是从子类（RedBlackTree）调用时，它使用父类的root字段而不是子类的root字段。

标签： javainheritance

解决方案

尝试将要重用的树逻辑移动到具有Node创建工厂方法的通用超类：

public abstract class AbstractBinarySearchTree<T extends Node> {
    protected T root;

    public T insert(int key) {
        T insertNode = newNode(key);
        // perform insertion
        return insertNode;
    }

    public abstract T newNode(int key);
}

具体的 BST 只需要工厂方法即可完成：

public class BinarySearchTree extends AbstractBinarySearchTree<Node> {
    @Override
    public Node newNode(int key) {
        return new Node(key);
    }
}

RBT 覆盖了插入方法和工厂方法：

public class RedBlackTree extends AbstractBinarySearchTree<RbtNode> {
    @Override
    public RbtNode insert(int key){
        RbtNode node = super.insert(key);
        // perform RBT fixes
        return node;
    }

    @Override
    public RbtNode newNode(int key) {
        return new RbtNode(key);
    }
}

推荐阅读