4.1. Binary Search Trees

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);
    }
}

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;
}

public T getKey() { return key; }

public N getParent() { return parent; }

public N getLeftChild() { return left_child; }

public N getRightChild() { return right_child; }

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;
}

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);
}

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

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;
    }
}

/** @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;
}

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;
}

/** @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;
}

/** @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);
}

/** @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;
}

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);
    }
}