4.1. Binary Search Trees

This section discusses abstraction of binary search trees.

This section assumes that you have already learned core concepts about binary search tress from the prerequisite. Thus, it focuses on the abstraction that can be applied to other types of binary search trees introduced in the following sections.

Abstract Binary Node

Let us create an abstract class, AbstractBinaryNode:

public abstract class AbstractBinaryNode<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> {
    protected T key;
    protected N parent;
    protected N left_child;
    protected N right_child;

    public AbstractBinaryNode(T key) {
        setKey(key);
    }
}

• L1: defines two generic types, T for the type of the key and N is for the type of the binary node.

• L8: calls the setKey() method to assign the value of key in L2.

Let us define boolean methods for the member fields:

public boolean hasParent() { return parent != null; }

public boolean hasLeftChild() { return left_child != null; }

public boolean hasRightChild() { return right_child != null; }

public boolean hasBothChildren() {
    return hasLeftChild() && hasRightChild();
}

/** @return true if the specific node is the left child of this node. */
public boolean isLeftChild(N node) {
    return left_child == node;
}

/** @return true if the specific node is the right child of this node. */
public boolean isRightChild(N node) {
    return right_child == node;
}

What is the input parameter node is null for the isLeftChild() and isRightChild() methods?

Let us then define getters to access the member fields:

public T getKey() { return key; }

public N getParent() { return parent; }

public N getLeftChild() { return left_child; }

public N getRightChild() { return right_child; }

We can also define helper methods inferred by the getters:

public N getGrandParent() {
    return hasParent() ? parent.getParent() : null;
}

@SuppressWarnings("unchecked")
public N getSibling() {
    if (hasParent()) {
        N parent = getParent();
        return parent.isLeftChild((N)this) ? parent.getRightChild() : parent.getLeftChild();
    }

    return null;
}

public N getUncle() {
    return hasParent() ? parent.getSibling() : null;
}

• L9: this needs to be casted to N since the input parameter of isLeftChild() is N.

Is it safe to downcast this to N?

Finally, let us define setters and their helper methods:

public void setKey(T key) { this.key = key; }

public void setParent(N node) { parent = node; }

public void setLeftChild(N node) {
    replaceParent(node);
    left_child = node;
}

public void setRightChild(N node) {
    replaceParent(node);
    right_child = node;
}

/**
 * Replaces the parent of the specific node to be this node. 
 * @param node the node whose parent to be replaced.
 */
@SuppressWarnings("unchecked")
protected void replaceParent(N node) {
    if (node != null) {
        if (node.hasParent()) node.getParent().replaceChild(node, null);
        node.setParent((N)this);
    }
}

/**
 * Replaces the old child with the new child if exists.
 * @param oldChild the old child of this node to be replaced.
 * @param newChild the new child to be added to this node.
 */
public void replaceChild(N oldChild, N newChild) {
    if (isLeftChild(oldChild)) setLeftChild(newChild);
    else if (isRightChild(oldChild)) setRightChild(newChild);
}

• L5,10: sets node to be a child of this in two steps:

  • L6,11: replaces the parent of node with this.

  • L7,12: sets node to be the child.

• L20: replaces the parent of node with this in two steps:

  • L22: node gets abandoned by its current parent.

  • L23: this becomes the new parent of node.

• L32: replaces oldChild of this node with newChild.

Binary Node

Let us define the BinaryNode class inheriting AbstractBinaryNode:

public class BinaryNode<T extends Comparable<T>> extends AbstractBinaryNode<T, BinaryNode<T>> {
    public BinaryNode(T key) {
        super(key);
    }
}

• L1: defines only 1 generic type T for the comparable key and passes itself for the generic type N to theAbstractBinaryNode class.

Is there any abstract method from AbstractBinaryNode to be defined in BinaryNode?

Abstract Binary Search Tree

Let us define an abstract class, AbstractBinarySearchTree:

public abstract class AbstractBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> {
    protected N root;

    public AbstractBinarySearchTree() {
        setRoot(null);
    }

    /** @return a new node with the specific key. */
    abstract public N createNode(T key);
    
    public boolean isRoot(N node) { return root == node; }

    public N getRoot() { return root; }

    public void setRoot(N node) {
        if (node != null) node.setParent(null);
        root = node;
    }
}

• L1: defines two generic types, T for the type of the key and N is for the type of the binary node.

• L4: initializes the member field root to null.

• L9: creates a binary node typed N, required for the add() method.

Why does Java not allow a generic type to be instantiated (e.g., node = new N())?

Let us define searching methods:

/** @return the node with the specific key if exists; otherwise, {@code null}. */
public N get(T key) {
    return findNode(root, key);
}

/** @return the node with the specific key if exists; otherwise, {@code null}. */
protected N findNode(N node, T key) {
    if (node == null) return null;
    int diff = key.compareTo(node.getKey());

    if (diff < 0)
        return findNode(node.getLeftChild(), key);
    else if (diff > 0)
        return findNode(node.getRightChild(), key);
    else
        return node;
}

/** @return the node with the minimum key under the subtree of {@code node}. */
protected N findMinNode(N node) {
    return node.hasLeftChild() ? findMinNode(node.getLeftChild()) : node;
}

/** @return the node with the maximum key under the subtree of {@code node}. */
protected N findMaxNode(N node) {
    return node.hasRightChild() ? findMaxNode(node.getRightChild()) : node;
}

What are the worst-case complexities of findNode(), findMinNode(), and findMaxNode()?

Let us define the add() method:

public N add(T key) {
    N node = null;

    if (root == null)
        setRoot(node = createNode(key));
    else
        node = addAux(root, key);

    return node;
}

private N addAux(N node, T key) {
    int diff = key.compareTo(node.getKey());
    N child, newNode = null;

    if (diff < 0) {
        if ((child = node.getLeftChild()) == null)
            node.setLeftChild(newNode = createNode(key));
        else
            newNode = addAux(child, key);
    }
    else if (diff > 0) {
        if ((child = node.getRightChild()) == null)
            node.setRightChild(newNode = createNode(key));
        else
            newNode = addAux(child, key);
    }

    return newNode;
}

• L5: creates a node with the key to be the root if this tree does not include any node.

• L7: finds the appropriate location for the key and creates the node.

What does the add() method above do when the input key already exists in the tree?

Let us define the remove() method:

/** @return the removed node with the specific key if exists; otherwise, {@code null}. */
public N remove(T key) {
    N node = findNode(root, key);

    if (node != null) {
        if (node.hasBothChildren()) removeHibbard(node);
        else removeSelf(node);
    }

    return node;
}

• L6: removes a node with two children using the Hibbard algorithm.

• L7: removes a node with no or one child

The removeSelf() method makes the node's only child as the child of its parent and removes it:

/** @return the lowest node whose subtree has been updatede. */
protected N removeSelf(N node) {
    N parent = node.getParent();
    N child = null;

    if (node.hasLeftChild()) child = node.getLeftChild();
    else if (node.hasRightChild()) child = node.getRightChild();
    replaceChild(node, child);

    return parent;
}

private void replaceChild(N oldNode, N newNode) {
    if (isRoot(oldNode))
        setRoot(newNode);
    else
        oldNode.getParent().replaceChild(oldNode, newNode);
}

• L6: finds the child of node.

• L7: replaces node with its child.

The removeHibbard() method finds a node that can be the parent of the left- and the right-children of node and makes it a child of its parent:

Which nodes are guaranteed to be the parent of those left- and right- children?

/** @return the lowest node whose subtree has been updatede. */
protected N removeHibbard(N node) {
    N successor = node.getRightChild();
    N min = findMinNode(successor);
    N parent = min.getParent();

    min.setLeftChild(node.getLeftChild());

    if (min != successor) {
        parent.setLeftChild(min.getRightChild());
        min.setRightChild(successor);
    }

    replaceChild(node, min);
    return parent;
}

The following demonstrates how the above removeHibbard() method works:

What is the worst-case complexity of the removeHibbard() method?

Binary Search Tree

Let us define the BinarySearchTree inheriting AbstractBinarySearchTree:

public class BinarySearchTree<T extends Comparable<T>> extends AbstractBinarySearchTree<T, BinaryNode<T>> {
    /**
     * @param key the key of this node.
     * @return a binary node with the specific key.
     */
    @Override
    public BinaryNode<T> createNode(T key) {
        return new BinaryNode<T>(key);
    }
}