1 of 6

4. Binary Search Trees

This chapter discusses binary search trees using different balancing algorithms.

Binary Search Trees
Balanced BST
AVL Trees
Red-Black Trees
Quiz

References

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

4.2. Balanced BST

This section discusses abstraction of binary search trees.

A binary search tree gives the worst-case complexity of $O(n)$ for searching a key when it is not balanced, where $n$ is the number of nodes in the tree:

Insert

Delete

Unbalanced

Balanced

To ensure the $O(\log n)$ complexity, it needs to be balanced at all time (or at most time).

Rotation

There are 4 cases of unbalanced trees to be considered:

Left linear $\Rightarrow$ [3, 2, 1]
Right linear $\Rightarrow$ [1, 2, 3]
Left zig-zag $\Rightarrow$ [3, 1, 2]
Right zig-zag $\Rightarrow$ [1, 3, 2]

These cases can be balanced by performing rotations as follows:

What should happen to the subtrees (red/orange/green/blue triangles) after the rotations?

Abstract Balanced Binary Search Tree

Let us create an abstract class AbstractBalancedBinarySearchTree that inherits the abstract class AbstractBinarySearchTree:

public abstract class AbstractBalancedBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> extends AbstractBinarySearchTree<T, N> {
    /**
     * Rotates the specific node to the left.
     * @param node the node to be rotated.
     */
    protected void rotateLeft(N node) {
        N child = node.getRightChild();
        node.setRightChild(child.getLeftChild());

        if (node.hasParent())
            node.getParent().replaceChild(node, child);
        else
            setRoot(child);

        child.setLeftChild(node);
    }

    /**
     * Rotates the specific node to the right.
     * @param node the node to be rotated.
     */
    protected void rotateRight(N node) {
        N child = node.getLeftChild();
        node.setLeftChild(child.getRightChild());

        if (node.hasParent())
            node.getParent().replaceChild(node, child);
        else
            setRoot(child);

        child.setRightChild(node);
    }
}

Where does node end up being after the rotations?

The followings demonstrate how the rotateLeft() method works:

Let us override the add() and remove() methods that call the abstract method balance():

@Override
public N add(T key) {
    N node = super.add(key);
    balance(node);
    return node;
}

@Override
public N remove(T key) {
    N node = findNode(root, key);

    if (node != null) {
        N lowest = node.hasBothChildren() ? removeHibbard(node) : removeSelf(node);
        if (lowest != null && lowest != node) balance(lowest);
    }

    return node;
}

/**
 * Preserves the balance of the specific node and its ancestors.
 * @param node the node to be balanced.
 */
protected abstract void balance(N node);

L3: calls the add() method in the super class, AbstractBinarySearchTree.
L4: performs balancing on node that is just added.
L14: performs balancing on node that is the lowest node in the tree affected by this removal.
L24: defines a balancing algorithm for a specific type of balanced binary search trees.

What are the worst-case complexities of the add() and remove() methods above?

4.2. AVL Trees

This section discusses a type of balanced binary search trees called AVL Trees.

AVL (Adelson-Velsky and Landis) trees preserve the balance at all time by keeping track of the height of every node through a balance factor.

AVL Node

Let us create the class inheriting AbstractBinaryNode:

L2: keeps track of the height of this node.
L6: a node with no children has the height of 1.

We then override the setLeftChild() and setRigthChild() methods such that the height of this node gets adjusted accordingly with the new child by calling the resetHeights() method:

L15: adjusts the height of this node and its ancestors, recursively.
L20-22: retrieve the height of this node.
L24-27: resets the height of this node if different and makes the recursive call to its parent.

What are the heights of 3, 5, and 7 in the figure below when the height of 4 changes from 3 to 4?

Finally, we define the getBalanceFactor() method that returns the height difference between the left-subtree and the right-subtree of this node:

How can we tell if the node is unbalanced by using the balance factor?

AVL Tree

L10,16: resets the height of node after rotation.

node.resetHeights() does not reset heights of nodes in its subtree. Would this cause an issue?

We then override the balance() method:

L6: the left-subtree is longer.
- L9-10: the case of left zig-zag.
- L12: the case of left linear.
L14: the right-subtree is longer.
- L17: the case of right zig-zag.
- L20: the case of right linear.

The followings demonstrate how the balance() method works in AVL Trees:

What is the worst-case complexity of the balance() method in AVLTree?

4.3. Red-Black Trees

This section discusses a type of balanced binary search trees called Red-Black Trees.

Red-Black trees preserve the balance at most time by satisfying the following conditions:

Every node is either red or black.
The root and all leaves (null) are black.
Every red node must have two black children.
Every path from a given node to any of its leaves goes through the same number of black nodes.

Red-Black Node

Let us create the RedBlackNode class inheriting AbstractBinaryNode:

public class RedBlackNode<T extends Comparable<T>> extends AbstractBinaryNode<T, RedBlackNode<T>> {
    private boolean is_red;

    public RedBlackNode(T key) {
        super(key);
        setToRed();
    }

    public void setToRed() { is_red = true; }

    public void setToBlack() { is_red = false; }

    public boolean isRed() { return is_red; }

    public boolean isBlack() { return !is_red; }
}

L2: if is_red is true, the color of this node is red; otherwise, it is black.
L6: the color of the node is black by default upon instantiation.

Let us the RedBlackTree class inheriting AbstractBalancedBinarySearchTree:

public class RedBlackTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, RedBlackNode<T>> {
    @Override
    public RedBlackNode<T> createNode(T key) {
        return new RedBlackNode<T>(key);
    }
}

Finally, let us override balance() method that handles 3 cases:

@Override
protected void balance(RedBlackNode<T> node) {
    if (isRoot(node))
        node.setToBlack();
    else if (node.getParent().isRed()) {
        RedBlackNode<T> uncle = node.getUncle();

        if (uncle != null && uncle.isRed())
            balanceWithRedUncle(node, uncle);
        else
            balanceWithBlackUncle(node);
    }
}

L3: sets the color to black if node is the root.
L5: if the color of node's parent is red:
- L8: checks if the color of node's uncle is also red.
- L10: the color of node's uncle is black.

What about the case when the color of node's parent is black?

The following shows a method that handles when both the parent and the uncle are red:

private void balanceWithRedUncle(RedBlackNode<T> node, RedBlackNode<T> uncle) {
    node.getParent().setToBlack();
    uncle.setToBlack();
    RedBlackNode<T> grandParent = node.getGrandParent();
    grandParent.setToRed();
    balance(grandParent);
}

Are there any structural changes after this method is called?

The following shows a method that handles when the parent is red but the uncle is black:

private void balanceWithBlackUncle(RedBlackNode<T> node) {
    RedBlackNode<T> grandParent = node.getGrandParent();

    if (grandParent != null) {
        RedBlackNode<T> parent = node.getParent();

        if (grandParent.isLeftChild(parent) && parent.isRightChild(node)) {
            rotateLeft(parent);
            node = parent;
        }
        else if (grandParent.isRightChild(parent) && parent.isLeftChild(node)) {
            rotateRight(parent);
            node = parent;
        }

        node.getParent().setToBlack();
        grandParent.setToRed();

        if (node.getParent().isLeftChild(node))
            rotateRight(grandParent);
        else
            rotateLeft(grandParent);
    }
}

L7: the case of left zig-zag.
L11: the case of right zig-zag.
L19: the case of left linear.
L21: the case of right linear.

The followings demonstrate how the balance() method works in Red-Black trees:

How does a Red-Black tree know when it is unbalanced?

4.4. Quiz

This section provides exercises for better understanding in balanced binary search trees.

Interpretation

Explain how the remove() method works in the AbstractBalancedBinarySearchTree class:
- Explain what gets assigned to lowest in L71.
- Explain how the balance() methods in AVLTree and RedBlackTree keep the trees balanced (or fails to keep them balanced) after a removal.
Write a report including your explanation and save it as quiz4.pdf.

Implementation

Create the BalacnedBinarySearchTreeQuiz class under the tree.balanced package that inherits theAbstractBalancedBinarySearchTree class.
Override the balance() method that first checks the following conditions:
- node is the only child &
- node’s parent is the right child of node's grand parent &
- node’s uncle has only one child.
If all of the above conditions are satisfied, balance() makes multiple rotations such that the left subtree is always full before any node gets added to the right subtree.
For the example below, after adding the keys (in red) to the trees 1, 2, 3, and 4, they all need to be transformed into the tree 5 by the balance() method.
The transform must be performed only by rotations; other setter methods such as setLeftChild() or setRightChild() are not allowed in this assignment.

4.2. AVL Trees

This section discusses a type of balanced binary search trees called AVL Trees.

AVL (Adelson-Velsky and Landis) trees preserve the balance at all time by keeping track of the height of every node through a balance factor.

AVL Node

Let us create the class inheriting AbstractBinaryNode:

L2: keeps track of the height of this node.
L6: a node with no children has the height of 1.

We then override the setLeftChild() and setRigthChild() methods such that the height of this node gets adjusted accordingly with the new child by calling the resetHeights() method:

@Override
public void setLeftChild(AVLNode<T> node) {
    super.setLeftChild(node);
    resetHeights();
}

@Override
public void setRightChild(AVLNode<T> node) {
    super.setRightChild(node);
    resetHeights();
}

/** Resets the heights of this node and its ancestor, recursively. */
public void resetHeights() {
    resetHeightsAux(this);
}

private void resetHeightsAux(AVLNode<T> node) {
    if (node != null) {
        int lh = node.hasLeftChild() ? node.getLeftChild().getHeight() : 0;
        int rh = node.hasRightChild() ? node.getRightChild().getHeight() : 0;
        int height = Math.max(lh, rh) + 1;

        if (height != node.getHeight()) {
            node.setHeight(height);
            resetHeightsAux(node.getParent());  // recursively update parent height
        }
    }
}

L15: adjusts the height of this node and its ancestors, recursively.
L20-22: retrieve the height of this node.
L24-27: resets the height of this node if different and makes the recursive call to its parent.

What are the heights of 3, 5, and 7 in the figure below when the height of 4 changes from 3 to 4?

Finally, we define the getBalanceFactor() method that returns the height difference between the left-subtree and the right-subtree of this node:

/** @return height(left-subtree) - height(right-subtree). */
public int getBalanceFactor() {
    if (hasBothChildren())
        return left_child.getHeight() - right_child.getHeight();
    else if (hasLeftChild())
        return left_child.getHeight();
    else if (hasRightChild())
        return -right_child.getHeight();
    else
        return 0;
}

How can we tell if the node is unbalanced by using the balance factor?

AVL Tree

Let us create the class that inherits AbstractBalancedBinarySearchTree and override the createNote(), rotateLeft(), and rotateRight() methods:

public class AVLTree<T extends Comparable<T>> extends AbstractBalancedBinarySearchTree<T, AVLNode<T>> {
    @Override
    public AVLNode<T> createNode(T key) {
        return new AVLNode<>(key);
    }

    @Override
    protected void rotateLeft(AVLNode<T> node) {
        super.rotateLeft(node);
        node.resetHeights();
    }

    @Override
    protected void rotateRight(AVLNode<T> node) {
        super.rotateRight(node);
        node.resetHeights();
    }
}

L10,16: resets the height of node after rotation.

node.resetHeights() does not reset heights of nodes in its subtree. Would this cause an issue?

We then override the balance() method:

@Override
protected void balance(AVLNode<T> node) {
    if (node == null) return;
    int bf = node.getBalanceFactor();

    if (bf == 2) {
        AVLNode<T> child = node.getLeftChild();

        if (child.getBalanceFactor() == -1)
            rotateLeft(child);

        rotateRight(node);
    }
    else if (bf == -2) {
        AVLNode<T> child = node.getRightChild();

        if (child.getBalanceFactor() == 1)
            rotateRight(child);

        rotateLeft(node);
    }
    else
        balance(node.getParent());
}

L6: the left-subtree is longer.
- L9-10: the case of left zig-zag.
- L12: the case of left linear.
L14: the right-subtree is longer.
- L17: the case of right zig-zag.
- L20: the case of right linear.

The followings demonstrate how the balance() method works in AVL Trees:

What is the worst-case complexity of the balance() method in AVLTree?

4.1. Binary Search Trees

This section discusses abstraction of binary search trees.

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

4. Binary Search Trees

Contents

References

4.1. Binary Search Trees

Abstract Binary Node

Binary Node

Abstract Binary Search Tree

Binary Search Tree

4.2. Balanced BST

Rotation

Abstract Balanced Binary Search Tree

4.2. AVL Trees

AVL Node

AVL Tree

4.3. Red-Black Trees

Red-Black Node

4.4. Quiz

Interpretation

Implementation

4.4. Quiz

Interpretation

Implementation

4.2. AVL Trees

AVL Node

AVL Tree

4. Binary Search Trees

Contents

References

4.1. Binary Search Trees

Abstract Binary Node

Binary Node

Abstract Binary Search Tree

Binary Search Tree

4.3. Red-Black Trees

Red-Black Node

4.2. Balanced BST

Rotation

Abstract Balanced Binary Search Tree