Version: 0.4.24

2. Binary Search Trees#

Lecture:

Lecture 5.2 (slides)

Objectives:

Understand how to implement an ordered set using a binary search tree

Concepts:

Ordered Set ADT, insertion, deletion, min/max, predecessor/successor in a BST

We focus here on the binary search tree (BST), a tree data structure that implements ordered sets where items shall remain in a specific order at all times. Although the BST in its simplest form is not very efficient, we will later add *self-balancing* (see Lecture 5.4) to make it “production-ready”.

2.1. Ordered Sets#

An ordered set is a collection of unique items with a logical order. Take for instance books on a shelf, we could order them by title, provided there is not two books with the same title. The table below list some examples:

Table 2.3 Ten famous books ordered by title#

Title

Author

Pages

1984

George Orwell

328

Crime and Punishment

Fyodor Dostoevsky

671

Moby-Dick

Herman Melville

720

One Hundred Years of Solitude

Gabriel García Márquez

417

Pride and Prejudice

Jane Austen

279

The Catcher in the Rye

J.D. Salinger

234

The Great Gatsby

  1. Scott Fitzgerald

180

The Lord of the Rings

J.R.R. Tolkien

1178

To Kill a Mockingbird

Harper Lee

281

War and Peace

Leo Tolstoy

1225

Note that every book (the physical instances on the shelf) is unique, but I can order them in various ways: By title, by author, or by page count, etc.

Historical events is another example of “things” that are both unique and naturally ordered.

2.1.1. Formal Definition#

In mathematics an ordered set \(O\) is a pair \(O=(S, \leq)\), where:

  • \(S\) is a set

  • \(\leq\; \in S \times S\) is an ordering relationship over \(S\) such that:

    • \(S\) is reflexive, that is \(\forall a \in S, a \leq a\)

    • \(S\) is transitive, that is

      \[\forall (x,y,z) \in S³, \; x \leq y \land y \leq z \implies x \leq z\]

    • \(S\) is antisymmetric, that is:

      \[\forall (x,y) \in S², \; a \leq b \land b \leq a \iff a = b\]

    • \(S\) is total: It applies to every possible pair of items from \(S\),

      \[\forall (x,y) \in S², \; a \leq b \lor b \leq a\]

Returning to the books listed on Table 2.3, the book are the set \(O\), whereas the order I choose to organize my shelf is the relationship \(\leq\).

2.1.2. Abstract Data Type#

We define the oset ADT (see Lecture 2.1) to represent ordered sets. I focus here on operations that distinguish an ordered set from a “classical” set, but all other set operations such as union, intersection, difference, etc. remain meaningful.

oset.create() → OrderedSet#

Create an new empty ordered set \(o\).

Post-conditions

  • The ordered set \(o\) is empty, that is:

    \[o = create() \implies cardinal(o) = 0\]
oset.cardinal(o: OrderedSet) → Natural#

Returns the number of items in the given ordered set \(o\)

oset.contains(o: OrderedSet, i: Item) → Boolean#

Returns true if and only if \(i\) is a member of \(o\).

oset.minimum(o: OrderedSet) → Item#

Find the smallest item \(\alpha\) of the given ordered set \(o\).

Pre-conditions

  • The ordered set \(o\) is not empty, that is:

    \[cardinal(o) > 0\]
Post-conditions

  • There is no other item in \(o\) less than to \(alpha\), that is:

    \[\alpha = minimum(o) \implies \nexists\,i, \; contains(o, i) \land i < \alpha\]
oset.maximum(o: OrderedSet) → Item#

Find the largest item \(\omega\) of the given ordered set \(o\).

Pre-conditions

  • The ordered set \(o\) is not empty, that is:

    \[cardinal(o) > 0\]
Post-conditions

  • There is no other item \(i\) in \(o\) greater than to \(alpha\), that is:

    \[\omega = maximum(o) \implies \nexists\, i, \; contains(o,i) \land \omega < i\]
oset.successor(o: OrderedSet, i: Item) → Item#

Find the item \(j\) directly greater than the given item \(i\) in the ordered set \(o\).

Pre-conditions

  • The ordered set \(o\) contains the given item \(i\), that is:

    \[contains(o, i)\]

  • There exists at least one item in \(o\) that is greater than the given item \(i\).

    \[\exists k, i < k \land contains(o, k)\]
Post-conditions

  • The successor \(j\) is also a member of \(o\), that is:

    \[j = successor(o, i) \implies contains(o, j)\]

  • There is no other item \(k\) in \(o\) in between \(i\) and \(j\), that is:

    \[j = successor(o, i) \iff \nexists\, k , \; contains(o, k) \land i < k < j\]
oset.predecessor(o: OrderedSet, i: Item) → Item#

Find the item \(h\) directly smaller than the given item \(i\) in the ordered set \(o\).

Pre-conditions

  • The ordered set \(o\) contains the given item \(i\), that is:

    \[contains(o, i)\]

  • There exists at least one item \(k\) in \(o\) that is smaller than the given item \(i\).

    \[\exists k, k < i \land contains(o, k)\]
Post-conditions

  • The predecessor \(h\) is also a member of \(o\), that is:

    \[h = predecessor(o, i) \implies contains(o, h)\]

  • There is no other item \(k\) in \(o\) in between \(h\) and \(i\), that is:

    \[h = predecessor(o, i) \iff \nexists\, k , \; contains(o, k) \land h < k < i\]
oset.add(o: OrderedSet, i: Item) → OrderedSet#

Insert a new item in a given ordered set

Post-conditions

  • The given item \(i\) is added to the set \(o\) only if it is not already present, that is:

    \[\begin{split}o' = insert(o, i) \implies & contains(o', i) \\ & \land (\neg contains(o,i) \iff cardinal(o') = cardinal(o) + 1)\end{split}\]
oset.remove(o: OrderedSet, i: Item) → OrderedSet#

Remove an item \(i\) from the given ordered set \(o\).

Pre-conditions

  • The ordered set \(o\) is not empty, that is:

    \[cardinal(o) > 0\]
Post-conditions

  • The given item \(i\) is removed from the set \(o\) only if it is already present, that is:

    \[\begin{split}o' = remove(o, i) \implies & \neg\, contains(o', i) \\ & \land (contains(o, i) \iff cardinal(o') = cardinal(o) - 1)\end{split}\]

2.2. Ordered Set Using a Binary Search Tree#

A binary search tree (BST) is a tree data structure that offers an efficient implementation of the operations that characterize an ordered set, namely

Table 2.4 Summary of the Ordered Set Operations Efficiencies Using a BST#

Operation

Best-case

Worst-case

Average case

oset.cardinal()

\(O(n)\)

\(O(n)\)

\(O(n)\)

oset.contains()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.add()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.remove()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.minimum()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.maximum()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.predecessor()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

oset.successor()

\(O(1)\)

\(O(n)\)

\(O(\log n)\)

A BST is a binary tree (see Lecture 5.1): Every node has at most two children, often denoted as “left” and “right”. Besides its children, each node carries a item of the ordered set the tree represents.

Important

Every node carries an item that is greater than or equals to all the item in its left sub tree, and strictly smaller than all the items in its right sub tree.

../../_images/invariant.svg

Fig. 2.24 The invariant enforced by all BST nodes#

Consider the BST shown below on Fig. 2.25. It captures the ordered set formed by a few natural numbers. Take the root node: It carries 27 and every node on its left carries a smaller value, and every node on its right carries a larger value. Note how the tree reflects the natural ordering of numbers.

../../_images/example.svg

Fig. 2.25 A BST build from a few natural numbers#

Typescript Implementation

Following our blue print to implement trees (see Lecture 5.1) use a facade object that expose our ADT’s operations and access the root of the tree. Fig. 2.26 illustrates this approach using a UML class diagram.

../../_images/design.svg

Fig. 2.26 General implementation of a BST (UML class diagram)#

We are free to implement these operations using either iteration or recursion. Let see how that would look like in Typescript.

type Order<T> = (left: T, right: T) => boolean;

class OrderedSet<Item> {

    private _order: Order<Item>;
    private _root: Node<Item> | null;

    constructor(
        order: Order<Item>,
        root: Node<Item> | null) {
        this._order = order;
        this._root = root;
    }

}


class Node<Item> {

   item: Item;
   left: Node<Item> | null;
   right: Node<Item> | null;

   constructor (
       item: Item,
       left: Node<Item> | null,
       right: Node<Item> | null
   ) {
       this.item = item;
       this.left = left;
       this.right = right;
   }

}

2.2.1. Cardinal#

Let’s start with the simplest query: oset.cardinal(), which returns the number of items in set. The simplest way to compute it against a BST is to iterate over the nodes of the tree, using a DFS or a BFS (see Lecture 5.1).

Typescript Implementation

I use below a depth-first strategy (DFS), implemented using a loop and stack.

 1cardinal (): number {
 2    if (this.isEmpty) return 0;
 3    let cardinal = 0;
 4    const stack: Array<Node<Item>> = [this._root!]
 5    while (stack.length > 0) {
 6        const current = stack.pop();
 7        cardinal += 1;
 8        for (const eachChild of current!.children) {
 9            stack.push(eachChild)
10        }
11    }
12    return cardinal;
13}

This solution takes a time proportional to the number of nodes in tree. A faster approach is to store this count and to modify the oset.add() and oset.remove() commands to update this count. The oset.cardinal() then runs in constant time, in exchange of a negligible extra work when modifying the tree.

2.2.2. Membership#

How can we implement the oset.contains() using a BST? Why not just iterate through the nodes, checking whether any matches? That would work but would take as long as there are items in the tree (i.e., \(O(n)\)). We can do better if we leverage the structure of the BST.

Consider again a BST shown on Fig. 2.25 and say we are searching for 36. When we look at the root (i.e., 27) we know where to continue: 27 is smaller than 36, 36 has to be on the right subtree (if it is in the tree). As shown Fig. 2.27, we can exploit this to navigate “straight” to the target.

../../_images/contains.svg

Fig. 2.27 Searching for Item 36#

This algorithm can be summarized as:

  1. Take the root as our current node;

  2. We compare the item of our current node to our target;

  3. If this node has the item we are looking for, then we found it!

  4. If this item is smaller than our target, we set our current node to the left child, and continue at Step 2. If there is no left child, the target is not in the tree.

  5. If this item is larger than our target, we set our current node to the right child and continue at Step 2. If there is no right child, our target is not in the tree.

Typescript Implementation

I continue below the Typescript implementation we started earlier. Here is the body oft

 1class OrderedSet<Item> {
 2
 3    contains (target: Item): boolean {
 4         if (this.isEmpty) return false;
 5         let node = this._root;
 6         while (node != null) {
 7             if (this._order(node.item, target)) {
 8                 if (node.item == target) {
 9                     return true;
10
11                 } else {
12                     node = node.right;
13
14                 }
15             } else {
16                 node = node.left;
17
18             }
19         }
20         return false;
21     }
22
23 }
Why Is This Correct?

Our specification of oset.contains() returns true if and only if there exists a node that carries the given item \(i\). I would think recursively, and prove correctness by induction, as trees are recursive by definition. Let’s consider the base cases first:

  • If the tree is empty, we return false, which is correct: An empty tree contains nothing.

  • If the tree boils down to a single leaf node, then we return true if and only if the that node contains the given item.

Now we can make the induction step. Let’s assume our algorithm is correct for a tree of height \(h\), and show it works for a slightly larger tree of height \(h+1\). There are there cases:

  • If the root carries an item \(k\) that equals the given item \(i\), we return true. That is correct.

  • If the tree carries an item \(k\) smaller than the given item \(i\), then we apply our algorithm to its right subtree. This is correct by assumption: This right subtree has a height \(h\).

  • If the tree carries an item \(k\) that is larger than \(i\), then apply our algorithm to the left subtree. This is correct by assumption: The left subtree has a height \(h\).

Now we know that our algorithm works for a tree height 1 (the base cases) and, that given a tree of height \(h\) it would work for any tree of height \(h+1\) (the induction step), we therefore know it works for trees of any height.

How Efficient Is This?

This is the very same as the binary search algorithm (Lecture 2.4). Here is the efficiency depends on the depth of the branch we are navigating. In the best case, this branch is very short (we are searching for the root), and the search takes constant time (i.e., \(O(1)\)). In the worst case, the tree is one single long branch and the search takes as long as there are items in the tree (i.e., \(O(n)\)). In average however, the branch is a long as the height of the tree so the search takes logarithmic time (i.e., \(O(\log n)\)).

Exercise 2.1 (Recursive membership)

How would you implement the oset.contains() operation against a BST using recursion instead of iteration? Look at the discussion about correctness for some inspiration.

2.2.3. Minimum and Maximum#

How could we find the minimum and the maximum items of an ordered set against a BST? We could traverse the tree (i.e., use a DFS or BFS) but that would yield a linear runtime in all cases. We can be faster if we exploit the structure of the BST, which adheres to the ordering of items. The minimum is always the furthest on the left, and the maximum the furthest on the right.

As shown on Fig. 2.28, finding the minimum boils down to following the left branch as far as possible. Finding the maximum works the same way: We always “go right”.

  1. We start at the root, and make it our current node.

  2. If the current node has a left child,

    • Then, we update our current node, and return at Step 2.

    • Otherwise, we return the item carried by the current node.

../../_images/minimum.svg

Fig. 2.28 Finding the minimum in a BST by always going “left”#

Typescript Implementation

Our Typescript implementation closely resembles the contains operation, but looks simpler as we always continue along the left branch.

 1class OrderedSet<Item> {
 2
 3    minimum (): Item {
 4      if (this.isEmpty) {
 5          throw new Error(
 6              "Invalid state: An empty ordered set has no minimum."
 7          );
 8
 9      }
10      let node = this._root;
11      while (node != null && node.hasLeft) {
12          node = node.left;
13      }
14      return node!.item;
15   }
16
17}
Why Is This Correct?

Again, I would argue by induction over the recursive tree structure. Let’s start by the base case, there is only one.

  • When the tree is a single leaf node, the minimum is necessarily the value that this node carries, and that is what we return.

Now if we assume that our algorithm works for any tree of height \(h\), and that we are given a tree of height \(h+1\), there is only one case:

  • We return the minimum of the left subtree, which is correct, because it is necessarily smaller or equals than the item carried by the current node.

Since it works for the base case (leaves) and, if it works for trees of height \(h\), it also works for trees of height \(h + 1\) (inductive step), then, by structural induction, it works for all BSTs.

How Efficient Is This?

As for most queries on trees, it depends on the depth of the node that carries the desired item.

  • In the best case, this node is the root, and finding the minimum takes constant time.

  • In the worst case, the whole tree is a long thin left branch, and finding the minimum takes linear time.

  • In average, it takes a time that is proportional to the height of the tree, that is \(O(\log n)\).

Exercise 2.2 (Maximum)

The oset.maximum() is the symmetric of the oset.minimum(). How would you design it?

2.2.4. Predecessor and Successor#

Given a reference item, where is the predecessor located in a BST? It is the closest node to the left. There are however three possibilities:

  • It may be located among the descendants of the reference

  • It may be located among the ancestors of the reference

  • It may not exist, if the given reference is the minimum

Consider first Fig. 2.29 below, where we are looking for the predecessor of 39, which is 36. Since 39 has a left child, its predecessor is necessarily in the interval \((27, 39]\), which is its left subtree. Further, the predecessor is the maximum of this subtree, that is, the right-most node.

../../_images/predecessor_has_left.svg

Fig. 2.29 Finding the predecessor when the reference node has a left child: 36 is the maximum of the left subtree of 39.#

Consider now Fig. 2.30 below, where we are looking for the predecessor of 17, which is 12. Since 17 has no left subtree, its predecessor is necessarily its closest left-ancestor. This first left-ancestor, is necessarily the closest predecessor due to the BST invariant (see Fig. 2.24).

../../_images/predecessor_ancestor.svg

Fig. 2.30 Finding the predecessor when the reference node has no left subtree: 12 is the predecessor of 17.#

We can thus summarize the algorithm as follows:

  1. Find the node that carries the given item;

  2. If this node has a left subtree:

    • Then, we return the maximum of its left subtree;

    • Otherwise we return the first ancestor that is smaller than the current node (starting from the parent), or none if there is no such parent.

Typescript Implementation

Below is my Typescript implementation of the oset.predecessor() operation. It closely follows the algorithm I outlined above.

 1predecessorOf (item: Item): Item | undefined {
 2     if (this.isEmpty) {
 3         throw new Error(`Invalid state: Ordered set is empty.`)
 4
 5     }
 6     const path = this.findPathTo(item);
 7     if (path[path.length-1].item != item) {
 8         throw new Error(`Invalid state: Item '${item}' is not a member.`);
 9
10     } else {
11         const node = path.pop();
12         if (node!.hasLeft) {
13             return this.maximumFrom(node!.left!);
14
15         } else {
16             return this.firstSmallerAncestor(path, item);
17
18         }
19     }
20}

There are two “variations” around the code I presented so far:

  • Line 6, I use the findPathTo helper, which returns the list of ancestor to a given items, ordered from the root node. This simplifies search for the first smaller ancestor later on. If the given item cannot be found, it returns a path to the insertion point.

     1 private findPathTo(target: Item): Array<Node<Item>> {
 2     const path: Array<Node<Item>> = [];
 3     if (this.isEmpty) return path;
 4     let node = this._root;
 5     while (node != null) {
 6         path.push(node);
 7         if (this._order(node.item, target)) {
 8             if (node.item == target) {
 9                 break;
10             } else {
11                 node = node.right;
12             }
13         } else {
14             node = node.left;
15         }
16     }
17     return path;
18 }

  • Line 13, I use a findMaximumFrom operation that accepts a “root” node. That permits reusing the “maximum” algorithm on any node.

    1private maximumFrom(root: Node<Item>) {
2    let node = root;
3    while (node != null && node.hasRight) {
4        node = node.right!;
5    }
6    return node!.item;
7}

  • Line 16, I use the firstSmallerAncestor helper operation, which goes through a given path and find the first ancestor (starting from the end) that is smaller than the given item.

     1private firstLesserAncestor(
 2    path: Array<Node<Item>>,
 3    item: Item
 4): Item | undefined {
 5    while (path.length > 0) {
 6        const parent = path.pop();
 7        if (this._order(parent!.item, item)) {
 8            return parent!.item;
 9        }
10    }
11    return undefined;
12}
Why Is This Correct?

Because of the structure of BSTs, for any node, its predecessor is necessarily the “closest node to the left”. This “closest” node can be either amongst the ancestors or the descendants. Should both exist, the one in the descendants is always “closer” to the reference, and should thus be considered first. See the distances shown on Fig. 2.31 below.

../../_images/predecessor_proof.svg

Fig. 2.31 Closest left-node: Why ancestors are necessarily further away then descendants.#

How Efficient Is This?

Again, it depends on the shape of the tree.

  • In the best case, the reference is the root and its predecessor is the left child. That runs in constant time.

  • In the worst case, the tree is a single long and thin left branch, the reference is the next to last node, and its predecessor is the minimum. That runs in linear time.

  • In average, the reference is somewhere along a branch and the predecessor is either further down towards the leaves or amongst the ancestors. In that case, it runs in \(O(\log n)\).

Exercise 2.3 (Successor)

The oset.successor() is the symmetric of the oset.predecessor(). How would you design it?

2.2.5. Addition#

Let’s now look at the commands that modify the structure of tree. oset.add() is the first one: It adds a new item.

As we use a BST, we must guarantee that every node carries an item larger than any of its left subtree and smaller than any of its right subtree. To do that, we proceed as follows:

  1. We search for the right “parent” node by navigating the tree until we cannot progress anymore.

  2. If the item to insert is smaller or equals to parent

    • Then insert a new node as the left child

    • Otherwise insert a new node as the right child

Fig. 2.32 gives an example. To insert 28, we start from the root and navigate down the tree until we cannot progress anymore (just as the oset.contains() would do). We get stuck on Node 30, which has only a right subtree. Since 28 is smaller than 30, we insert it as a new left child.

../../_images/add.svg

Fig. 2.32 Insertion in a BST: 28 is placed as the left child of 30.#

Typescript Implementation

I reuse below the findPathTo which returns the path to the insertion point. The last node is the parent we have to modify. If the given item is smaller, I insert on the left, otherwise on the right.

 1add (newItem: Item) {
 2    if (this.isEmpty) {
 3        this._root = new Node<Item>(newItem, null, null);
 4
 5    } else {
 6        const path = this.findPathTo(newItem);
 7        const parent = path[path.length-1];
 8        if (this._order(newItem, parent.item)) {
 9            if (parent.item != newItem) {
10                parent.left = new Node<Item>(newItem, null, null)
11                this._cardinal += 1
12            }
13
14        } else {
15            parent.right = new Node<Item>(newItem, null, null);
16            this._cardinal += 1
17
18        }
19    }
20}
Why is it correct?

Our oset.add() specification requires that add be added if and only if it is not already present. We check for equality and before to insert on the left subtree.

However, The meaning of correctness is different for queries to commands. Not only the shall commands adhere its ADT specification, but commands shall also maintain the BST invariant.

This invariant requires that any node item be larger than any of its left subtree items, and smaller than any of its right subtree items. We assume that this invariant holds before the addition. Our procedure finds a parent that guarantees this invariant, and we add according to the invariant, so the invariant is preserved by the addition.

How efficient is it?

It depends on the structure of the tree, and the given item,

  • In the best case, the root is the parent and the insertion runs in constant time.

  • In the worst case, the tree is a single long thin branch, which we traverse all the way to its end to insert and the insertion takes a time linear to the size of the tree.

  • In average, the parent node has a depth that is proportional to the height of the tree, and the insertion runs in \(O(\log n)\).

Caution

What about duplicates? Intuitively, in a set, there is no duplicates but the ordering relationship \(\leq\) allows that. This ordering only decides precedence and not duplication, which is decided by the set itself. Take calendar events for instance: One can be “double booked” with two events at the same time, say Monday at 14:00. From the ordering perspective, these two events are equals, but these two events represents two different meetings, they are not duplicates. By default, a BST place duplicate on the left subtree as shown below:

../../_images/duplicates.svg

Fig. 2.33 Adding duplicates in a BST. 27 has been is added three times, but the tree remains a valid BST.#

2.2.6. Removal#

Removing an item from a BST is the most complicated procedure, because have to maintain the invariant of BST. When we delete a node we have to modify the tree for its subtrees to remain properly connected. There are two cases:

  • If the node to delete has only one child. We then connect the parent directly to the child of the deleted node (or null if there is no such child). In Fig. 2.34 illustrates the deletion of Node 21, which has only one child. We connect its parents (Node 12) to its child (Node 17) and remove Node 21.

    ../../_images/delete_one_child.svg

    Fig. 2.34 Deleting a node that has only one child, by connecting the child directly to its ancestor.#

  • If the node to delete has two children, we replace it by its predecessor. Fig. 2.35 shows the deletion of Node 39. We replace it by its predecessor, Node 36, which we delete.

    ../../_images/delete_two_children.svg

    Fig. 2.35 Deleting a node with two children by replacing it by its predecessor and deleting the predecessor#

I would summarize the algorithm as follows:

  1. We navigate down the tree to locate the item to delete

  2. Depending on the structure of this node

    1. If it has zero or one children

      • We connect its parents directly to the child node, or to nothing if there is no child node.

    2. If it has two children,

      1. We retrieve its predecessor

      2. We remove the predecessor (triggers necessarily Step 2.a)

      3. We replace the item by the predecessor

Typescript Implementation

The implementation below closely follows the algorithm outlined above. The main difference is that we first check if the tree is empty.

 1remove(item: Item) {
 2    if (this.isEmpty) {
 3        throw new Error("Invalid state: Ordered set is empty.");
 4
 5    } else {
 6        const path = this.findPathTo(item);
 7        const node = path.pop()
 8        if (node!.item != item) {
 9            throw new Error(`Invalid state: No item ${item}`);
10
11        } else {
12            const parent = path.pop()
13            if (node!.children.length < 2) {
14                if (parent) {
15                    parent.drop(node!)
16
17                } else {
18                    this._root = node!.children[0];
19
20                }
21
22            } else {
23                const predecessor = this.predecessorOf(node!.item);
24                this.remove(predecessor!);
25                node!.item = predecessor!;
26
27            }
28        }
29    }
30}

I encapsulate changing the parent node in the drop operation, that follows:

class Node<Item> {

    drop (child: Node<Item>) {
        const descendant = child.isLeaf ? null : child.children[0];
        if (this._left == child) {
            this._left = descendant;
        }
        if (this._right == child) {
            this._right = descendant;
        }
    }

}
Why Is It Correct?

How does that aligns with our definition oset.remove()? We remove item in the tree in all possible cases: When it is a leaf, when it has one child, and when it has two children. The next call to contains would return false. Now if the given item cannot be found, the tree is left unchanged.

Again, for the command oset.remove() we must also show that it guarantees the BST invariant. Let’s review the different cases:

  1. If the target node has no children, we just remove the node. This does not impact that ordering of the remaining nodes.

  2. If the target node has one child, we connect its parent to its child. Here for our algorithm to be correct, we update the left “pointer” of the parent whenever the target was its left child and the right pointer otherwise. If we update the left pointer, its “grandchild” was necessarily smaller, so that works. If we update the right side, the “grandchild” was necessarily larger. That works.

  3. If the target has two children, we replace it by its predecessor, which we delete. There are two possible positions for the predecessor: Either among the descendants, or amongst the ancestors. In our case, we know that our node has two children, so the predecessor is necessarily amongst the descendants. This predecessor is by definition the only value smaller than our node, also larger than all the other value in its left subtree. That would not change the ordering. Besides, when we delete this predecessor we know it cannot have two children (otherwise one if its right descendants would be the predecessor), so the deletion will be handled by a case (a) or (b). Note as well that the predecessor always exists, because deleting the minimum is handled by the case (a) or (b).

How Efficient Is This?

As for other operations, it depends on the “shape” of the tree. Let see the different scenario.

  • In the best case, we delete a leaf item in a short branch. This runs in constant time.

  • In the worst case, we delete the last item of a very long and thin branch. This runs in linear time.

  • In the average case, it depends on the height of the tree, as we often have to reach to the bottom of the branch to delete the node, either because we are deleting a leaf or because we are finding its predecessor.

Exercise 2.4 (Recursive Implementation)

How would you arrange a recursive version of this removal algorithm? Remember a tree is a recursive structure by definition.