Note: The passage is originally written in Chinese and translated into English via ChatGPT.

Reference: Lecture slides from 19sp.

Trees

First, the concept of abstract data type (ADT) is introduced, followed by a progressive/step-by-step optimization-based introduction to three types of trees (BST, B-Tree, LLRB).

The notes are divided into two parts, and this article only covers ADT and BST.

Abstract Data Types (ADT)

  • An abstract data type is defined by its operations, not implementations.
Hierarchy Examples
ADT Deque; DisjointSets
Implementations of ADT ArrayDeque, LinkedListDeque;
QuickFindDS, WeightedQuickUnionDS
Operations of ADT size(), get(), addFirst(Item x), etc.
  • Among the most important interfaces in the java.util library are those that extend the Collection interface. The relationship is shown in the figure.
    • List
    • Set
    • Map
image-20230327205326564
  • The focus this time is on two tree-related data types, TreeSet and TreeMap.

Binary Search Tree

Origins of BST

Question: How can we improve a linked list to perform searches more efficiently?

The answer is: 1) Set the entry point in the middle instead of one end. 2) Traverse from the middle to both ends. 3) Traverse in a skipping manner (as shown in the figure).

image-20230327210424890

Definition and Properties of BST

  • A binary search tree is a rooted binary tree with the BST property.
    • Tree properties:
      • A set of nodes
      • One path between any two nodes
    • Rooted tree properties:
      • Each node, except the root, has only one parent node.
      • The root is typically drawn at the top.
      • For binary trees, each node can have 0/1/2 child nodes.
    • BST properties:
      • Ordering: Every key in the left subtree is less than X’s key. Every key in the right subtree is greater than X’s key.
      • No duplicate keys are allowed.
image-20230327211546048

(Encountering a BST)

BST Operations

Three operations of BST are introduced.

Search / Find

Code Implementation

(It’s easier to understand through the code.) Compare searchKey with T.key –> Found! / searchKey is smaller, search T.left / searchKey is larger, search T.right.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// reference: Algorithms, p.399
/** Return value associated with key in the subtree rooted at x;
 *  return null if key not present in subtree rooted at x.
 */
public Value get(Key key) {
    return get(root, key);
}

private Value get(Node x, Key key) { // helper
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) {
        return get(x.left, key);
    } else if (cmp > 0) {
        return get(x.right, key);
    } else {
        return x.val;
    }
}
Runtime Analysis
  • Worst-case runtime: $\Theta(\log{N})$ for a dense binary tree.
  • Tree height: ~$\log_2{(N)}$
    • Consider the fact that each additional level requires twice the number of nodes.

Insert

Code Implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

/** Search for key. Update value if found; grow table if new. */
public void put(Key key, Value val) {
    root = put(root, key, val);
}
/** Change key's value to val if key in subtree rooted at x.
 *  Otherwise, add a new node to the subtree associating key with val. */
private Node put(Node x, Key key, Value val) {
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key); // compare searchKey to curKey
    if (cmp < 0) {
        x.left = put(x.left, key, val);
    } else if (cmp > 0) {
        x.right = put(x.right, key, val);
    } else {
        x.val = val;
    }
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}
Runtime Analysis for Insertion

It should be the same as the search operation.

Delete

There are three cases for deletion:

  • The key to be deleted has no child nodes (–> see “glut,” simply disconnect).
  • The key to be deleted has one child node (–> see “flat,” update the parent node’s pointer to the child node).
  • The key to be deleted has two child nodes (as shown in the figure, find the predecessor or successor to replace its position).
Code Implementation (p.411)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

private Node min(Node x) {              // Find the smallest node and its child nodes under x
    if (x.left == null) return x;
    return min(x.left);
}

public void deleteMin() {               // Return the root after deleting the smallest node
    root = deleteMin(root);
}

private Node deleteMin(Node x) {         // DeleteMin helper
    if (x.left == null) return x.right;
    x.left = deleteMin(x.left);
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

public void delete(Key key) {
    root = delete(root, key);
}

private Node delete(Node x, Key key) {
    if (x == null) return null;
    int cmp = key.compareTo(x.key);
    if (cmp < 0) {
        x.left = delete(x.left, key);
    } else if (cmp > 0) {
        x.right = delete(x.right, key);
    } else {                                // Assume the node P to be deleted has been found
        if (x.right == null) return x.left;  // Check if P has sub-nodes, A) if it has 0/1 sub-nodes, return it
        if (x.left == null) return x.right;
        Node t = x;                         // B) if it has 2 nodes, the tree needs to be adjusted
        x = min(t.right);                   // 1. Find the new substitute for the deleted node P
        x.right = deleteMin(t.right);       // 2. Connect the updated right nodes to the new P
        x.left = t.left;                    // 3. Connect the original left sub-nodes to the new P
        // Note the order matters here!
    }
    x

.N = size(x.left) + size(x.right) + 1;
    return x;
}
Runtime Analysis

It should be of the same order as the previous operations since it only involves additional modification steps.

BSTSet v.s. BSTMap

This part introduces Lab9 BSTmap.

BSTSet and BSTMap have the same structure (a tree), but the difference is that each node is represented using a map (as shown in the figure).