Symbol Tables

Updated: 03 January 2025

Notes based on Algorithms, Part 1 on Coursera

Symbol Table API

The idea is to have some kind of key-value association

Insert a value with a specified key
Given a key, search for the corresponding value

Basic Table API

The basic idea is to use an Associative Array such that we have the following definition:

1
export type Key = string | number
2

3
export interface SymbolTable<K extends Key, V> {
4
  /**
5
   * Put a value at a given key
6
   */
7
  put(key: K, value: V): void
8

9
  /**
10
   * Get a value given a key
11
   */
12
  get(key: K): V | undefined
13

14
  /**
15
   * Delete the value with the given key
16
   */
17
  delete(key: K): void
18

19
  /**
20
   * Check if the key/value exists in the symbol table
21
   */
22
  contains(key: K): boolean
23

24
  /**
25
   * Check if the symbol table is empty
26
   */
27
  isEmpty(): boolean
28

29
  /**
30
   * Get the total number of key value pairs in the symbol table
31
   */
32
  size(): number
33

34
  /**
35
   * Iterate through all keys in the table
36
   */
37
  keys(): Iterator<K>
38
}

Keys and Values

For Values:

Values are non-null
Put overwrites an old value

For Keys:

comparable since it enables us to do some more efficient algorithms
Immutable types for keys
Assume keys have some method for testing equality

The requirements for equality are as follows:

Reflexive - x == x
Symmetric: x == y iif y == x
Transitive: if x == y and x == z then x == y
Java also has: Non-null: x == null is false

For the sake of simplicity we’ll keep our implementation of keys to types that can be compared directly using the javascript === operator

Elementary Implementation

Unordered List/Sequential Search
- We could keep a list with a key-value pair in the array
- Putting requires us to run through and see if the value is already there and overwrite that value or add a new one at the end
- Getting a value requires us to scan through the entire array till we find the value
Ordered List/Binary Search
- We can use a binary search implementation in which we sort based on the key
- This will then have the same characteristics of a binary search for retreiving values
- With binary search however, we need to keep the items in order which makes insertions and deletions expensive as we need to shift all items to the right of our key
- Good for read-heavy usecases

Implementation	Worst Case	Average Case	Ordered iteration	Key interface
sequential search	N search, N insert	N/2 search, N insert	No	Equality
binary search	log N search, N insert	log N search, N/2 insert	yes	Comparison

The best above implementation is the binary search but it’s still fairly slow for insertion - we want to find an implementation that’s more efficient than this

Ordered Operations

When considering a symbol table it may sometimes be relevant to do things like

Get the min value
Get the max value
Get a value given a key
Get X top values
Get some list of keys ina a range
Floor/Ciel of a key

The API for an ordered symbol table is as follows

1
export type Key = string | number
2

3
export interface SymbolTable<K extends Key, V> {
4
  /**
5
   * Put a value at a given key
6
   */
7
  put(key: K, value: V): void
8

9
  /**
10
   * Get a value given a key
11
   */
12
  get(key: K): V | undefined
13

14
  /**
15
   * Delete the value with the given key
16
   */
17
  delete(key: K): void
18

19
  /**
20
   * Check if the key/value exists in the symbol table
21
   */
22
  contains(key: K): boolean
23

24
  /**
25
   * Check if the symbol table is empty
26
   */
27
  isEmpty(): boolean
28

29
  /**
30
   * Get the total number of key value pairs in the symbol table
31
   */
32
  size(): number
33

34
  /**
35
   * Iterate through all keys in the table
36
   */
37
  keys(): Iterator<K>
38
}

Binary Search Trees

Enables us to provide an efficient implementation of symbol tables

Binary search trees are binary trees that are in symmetric order - links in the tree can be null

A binary tree is either:

Empty
Two disjoint trees

In a binary search tree each node has a key and every key is larger than all trees in its left subtree and larger than all keys in its right subtree

To implement this we will extend the implementation of a linked list which is doubly linked such

BST Operations

Get

When searching a binary tree, we start at the root and compare the value:

If less - go left
If greater - go right
If equal - return the value

If we end up on a null link that means the value is not in the tree so we return null

The implementation of this can be seen below:


32 collapsed lines
1
import { Comparison, type Compare } from '../sorting/definition'
2
import type { Key } from './definition'
3

4
class Node<K extends Key, V> {
5
  readonly key: K
6
  val: V
7

8
  /**
9
   * Reference to smaller keys
10
   */
11
  left?: Node<K, V>
12

13
  /**
14
   * Reference to larger keys
15
   */
16
  right?: Node<K, V>
17

18
  constructor(key: K, val: V) {
19
    this.key = key
20
    this.val = val
21
  }
22
}
23

24
export class BinarySearchTree<K extends Key, V> {
25
  protected root?: Node<K, V>
26

27
  private readonly compare: Compare<K>
28

29
  constructor(compare: Compare<K>) {
30
    this.compare = compare
31
  }
32

33
  public get(key: K): V | undefined {
34
    let x: Node<K, V> = this.root
35

36
    while (x !== undefined) {
37
      const cmp = this.compare(key, x.key)
38

39
      if (cmp === Comparison.Less) x = x.left
40
      else if (cmp === Comparison.Greater) x = x.right
41
      else return x.val
42
    }
43

44
    return undefined
45
  }
82 collapsed lines
46

47
  private putAtNode(
48
    x: Node<K, V> | undefined,
49
    key: K,
50
    val: V,
51
  ): Node<K, V> | undefined {
52
    if (x === undefined) return new Node(key, val)
53

54
    const cmp = this.compare(key, x.key)
55

56
    if (cmp === Comparison.Less) x.left = this.putAtNode(x.left, key, val)
57
    else if (cmp === Comparison.Greater)
58
      x.right = this.putAtNode(x.right, key, val)
59
    else x.val = val
60

61
    return x
62
  }
63

64
  public put(key: K, val: V): void {
65
    this.root = this.putAtNode(this.root, key, val)
66
  }
67

68
  public max(): K | undefined {
69
    let x = this.root
70
    while (x.right) x = x.right
71

72
    return x.key
73
  }
74

75
  public min(): K | undefined {
76
    let x = this.root
77
    while (x.left) x = x.left
78

79
    return x.key
80
  }
81

82
  private floorOfNode(
83
    x: Node<K, V> | undefined,
84
    key: K,
85
  ): Node<K, V> | undefined {
86
    if (x === undefined) {
87
      return undefined
88
    }
89

90
    const cmp = this.compare(key, x.key)
91
    if (cmp === Comparison.Equal) return x
92

93
    if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)
94

95
    const t = this.floorOfNode(x.right, key)
96
    if (t) return t
97
    else return x
98
  }
99

100
  public floor(key: K): K | undefined {
101
    const x = this.floorOfNode(this.root, key)
102
    return x?.key
103
  }
104

105
  private ceilOfNode(
106
    x: Node<K, V> | undefined,
107
    key: K,
108
  ): Node<K, V> | undefined {
109
    if (x === undefined) {
110
      return undefined
111
    }
112

113
    const cmp = this.compare(key, x.key)
114
    if (cmp === Comparison.Equal) return x
115

116
    if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)
117

118
    const t = this.ceilOfNode(x.left, key)
119
    if (t) return t
120
    else return x
121
  }
122

123
  public ceil(key: K): K | undefined {
124
    const x = this.ceilOfNode(this.root, key)
125
    return x?.key
126
  }
127
}

Insert

Follow a similar process as we did for searching, but when we get to a null node then we insert the new node there

An important distinction in the insertion implementation is that we recursively traverse the child branches and modify the parent


45 collapsed lines
1
import { Comparison, type Compare } from '../sorting/definition'
2
import type { Key } from './definition'
3

4
class Node<K extends Key, V> {
5
  readonly key: K
6
  val: V
7

8
  /**
9
   * Reference to smaller keys
10
   */
11
  left?: Node<K, V>
12

13
  /**
14
   * Reference to larger keys
15
   */
16
  right?: Node<K, V>
17

18
  constructor(key: K, val: V) {
19
    this.key = key
20
    this.val = val
21
  }
22
}
23

24
export class BinarySearchTree<K extends Key, V> {
25
  protected root?: Node<K, V>
26

27
  private readonly compare: Compare<K>
28

29
  constructor(compare: Compare<K>) {
30
    this.compare = compare
31
  }
32

33
  public get(key: K): V | undefined {
34
    let x: Node<K, V> = this.root
35

36
    while (x !== undefined) {
37
      const cmp = this.compare(key, x.key)
38

39
      if (cmp === Comparison.Less) x = x.left
40
      else if (cmp === Comparison.Greater) x = x.right
41
      else return x.val
42
    }
43

44
    return undefined
45
  }
46

47
  private putAtNode(
48
    x: Node<K, V> | undefined,
49
    key: K,
50
    val: V,
51
  ): Node<K, V> | undefined {
52
    if (x === undefined) return new Node(key, val)
53

54
    const cmp = this.compare(key, x.key)
55

56
    if (cmp === Comparison.Less) x.left = this.putAtNode(x.left, key, val)
57
    else if (cmp === Comparison.Greater)
58
      x.right = this.putAtNode(x.right, key, val)
59
    else x.val = val
60

61
    return x
62
  }
63

64
  public put(key: K, val: V): void {
65
    this.root = this.putAtNode(this.root, key, val)
66
  }
61 collapsed lines
67

68
  public max(): K | undefined {
69
    let x = this.root
70
    while (x.right) x = x.right
71

72
    return x.key
73
  }
74

75
  public min(): K | undefined {
76
    let x = this.root
77
    while (x.left) x = x.left
78

79
    return x.key
80
  }
81

82
  private floorOfNode(
83
    x: Node<K, V> | undefined,
84
    key: K,
85
  ): Node<K, V> | undefined {
86
    if (x === undefined) {
87
      return undefined
88
    }
89

90
    const cmp = this.compare(key, x.key)
91
    if (cmp === Comparison.Equal) return x
92

93
    if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)
94

95
    const t = this.floorOfNode(x.right, key)
96
    if (t) return t
97
    else return x
98
  }
99

100
  public floor(key: K): K | undefined {
101
    const x = this.floorOfNode(this.root, key)
102
    return x?.key
103
  }
104

105
  private ceilOfNode(
106
    x: Node<K, V> | undefined,
107
    key: K,
108
  ): Node<K, V> | undefined {
109
    if (x === undefined) {
110
      return undefined
111
    }
112

113
    const cmp = this.compare(key, x.key)
114
    if (cmp === Comparison.Equal) return x
115

116
    if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)
117

118
    const t = this.ceilOfNode(x.left, key)
119
    if (t) return t
120
    else return x
121
  }
122

123
  public ceil(key: K): K | undefined {
124
    const x = this.ceilOfNode(this.root, key)
125
    return x?.key
126
  }
127
}

Tree Shape

In the case of a BST the number of compares in the above operations is 1+node depth

Depending on how insertion works, we can end up in a tree which is heavily skewed which can lead to varying performance. The performance of this may be very bad in the event that the inserts are done in some kind of ordered way

The implementation of a BST is very similar to the idea behind how quicksort works

Ordered BST Operations

Max and Min

To find the max value just keep moving right and to find the min value we just keep moving to the left


67 collapsed lines
1
import { Comparison, type Compare } from '../sorting/definition'
2
import type { Key } from './definition'
3

4
class Node<K extends Key, V> {
5
  readonly key: K
6
  val: V
7

8
  /**
9
   * Reference to smaller keys
10
   */
11
  left?: Node<K, V>
12

13
  /**
14
   * Reference to larger keys
15
   */
16
  right?: Node<K, V>
17

18
  constructor(key: K, val: V) {
19
    this.key = key
20
    this.val = val
21
  }
22
}
23

24
export class BinarySearchTree<K extends Key, V> {
25
  protected root?: Node<K, V>
26

27
  private readonly compare: Compare<K>
28

29
  constructor(compare: Compare<K>) {
30
    this.compare = compare
31
  }
32

33
  public get(key: K): V | undefined {
34
    let x: Node<K, V> = this.root
35

36
    while (x !== undefined) {
37
      const cmp = this.compare(key, x.key)
38

39
      if (cmp === Comparison.Less) x = x.left
40
      else if (cmp === Comparison.Greater) x = x.right
41
      else return x.val
42
    }
43

44
    return undefined
45
  }
46

47
  private putAtNode(
48
    x: Node<K, V> | undefined,
49
    key: K,
50
    val: V,
51
  ): Node<K, V> | undefined {
52
    if (x === undefined) return new Node(key, val)
53

54
    const cmp = this.compare(key, x.key)
55

56
    if (cmp === Comparison.Less) x.left = this.putAtNode(x.left, key, val)
57
    else if (cmp === Comparison.Greater)
58
      x.right = this.putAtNode(x.right, key, val)
59
    else x.val = val
60

61
    return x
62
  }
63

64
  public put(key: K, val: V): void {
65
    this.root = this.putAtNode(this.root, key, val)
66
  }
67

68
  public max(): K | undefined {
69
    let x = this.root
70
    while (x.right) x = x.right
71

72
    return x.key
73
  }
74

75
  public min(): K | undefined {
76
    let x = this.root
77
    while (x.left) x = x.left
78

79
    return x.key
80
  }
47 collapsed lines
81

82
  private floorOfNode(
83
    x: Node<K, V> | undefined,
84
    key: K,
85
  ): Node<K, V> | undefined {
86
    if (x === undefined) {
87
      return undefined
88
    }
89

90
    const cmp = this.compare(key, x.key)
91
    if (cmp === Comparison.Equal) return x
92

93
    if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)
94

95
    const t = this.floorOfNode(x.right, key)
96
    if (t) return t
97
    else return x
98
  }
99

100
  public floor(key: K): K | undefined {
101
    const x = this.floorOfNode(this.root, key)
102
    return x?.key
103
  }
104

105
  private ceilOfNode(
106
    x: Node<K, V> | undefined,
107
    key: K,
108
  ): Node<K, V> | undefined {
109
    if (x === undefined) {
110
      return undefined
111
    }
112

113
    const cmp = this.compare(key, x.key)
114
    if (cmp === Comparison.Equal) return x
115

116
    if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)
117

118
    const t = this.ceilOfNode(x.left, key)
119
    if (t) return t
120
    else return x
121
  }
122

123
  public ceil(key: K): K | undefined {
124
    const x = this.ceilOfNode(this.root, key)
125
    return x?.key
126
  }
127
}

Floor and Ceil

To get the floor we need to consider the following:

K is equal to the key at the root = the floor is K
K is less than the key at the root = the floor is in the left subtree
K is greater than the key at the root = the floor is in the right subtree

The ceiling implementation is the same but we traverse the other way instead. We can see the two implementations below:


81 collapsed lines
1
import { Comparison, type Compare } from '../sorting/definition'
2
import type { Key } from './definition'
3

4
class Node<K extends Key, V> {
5
  readonly key: K
6
  val: V
7

8
  /**
9
   * Reference to smaller keys
10
   */
11
  left?: Node<K, V>
12

13
  /**
14
   * Reference to larger keys
15
   */
16
  right?: Node<K, V>
17

18
  constructor(key: K, val: V) {
19
    this.key = key
20
    this.val = val
21
  }
22
}
23

24
export class BinarySearchTree<K extends Key, V> {
25
  protected root?: Node<K, V>
26

27
  private readonly compare: Compare<K>
28

29
  constructor(compare: Compare<K>) {
30
    this.compare = compare
31
  }
32

33
  public get(key: K): V | undefined {
34
    let x: Node<K, V> = this.root
35

36
    while (x !== undefined) {
37
      const cmp = this.compare(key, x.key)
38

39
      if (cmp === Comparison.Less) x = x.left
40
      else if (cmp === Comparison.Greater) x = x.right
41
      else return x.val
42
    }
43

44
    return undefined
45
  }
46

47
  private putAtNode(
48
    x: Node<K, V> | undefined,
49
    key: K,
50
    val: V,
51
  ): Node<K, V> | undefined {
52
    if (x === undefined) return new Node(key, val)
53

54
    const cmp = this.compare(key, x.key)
55

56
    if (cmp === Comparison.Less) x.left = this.putAtNode(x.left, key, val)
57
    else if (cmp === Comparison.Greater)
58
      x.right = this.putAtNode(x.right, key, val)
59
    else x.val = val
60

61
    return x
62
  }
63

64
  public put(key: K, val: V): void {
65
    this.root = this.putAtNode(this.root, key, val)
66
  }
67

68
  public max(): K | undefined {
69
    let x = this.root
70
    while (x.right) x = x.right
71

72
    return x.key
73
  }
74

75
  public min(): K | undefined {
76
    let x = this.root
77
    while (x.left) x = x.left
78

79
    return x.key
80
  }
81

82
  private floorOfNode(
83
    x: Node<K, V> | undefined,
84
    key: K,
85
  ): Node<K, V> | undefined {
86
    if (x === undefined) {
87
      return undefined
88
    }
89

90
    const cmp = this.compare(key, x.key)
91
    if (cmp === Comparison.Equal) return x
92

93
    if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)
94

95
    const t = this.floorOfNode(x.right, key)
96
    if (t) return t
97
    else return x
98
  }
99

100
  public floor(key: K): K | undefined {
101
    const x = this.floorOfNode(this.root, key)
102
    return x?.key
103
  }
104

105
  private ceilOfNode(
106
    x: Node<K, V> | undefined,
107
    key: K,
108
  ): Node<K, V> | undefined {
109
    if (x === undefined) {
110
      return undefined
111
    }
112

113
    const cmp = this.compare(key, x.key)
114
    if (cmp === Comparison.Equal) return x
115

116
    if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)
117

118
    const t = this.ceilOfNode(x.left, key)
119
    if (t) return t
120
    else return x
121
  }
122

123
  public ceil(key: K): K | undefined {
124
    const x = this.ceilOfNode(this.root, key)
125
    return x?.key
126
  }
1 collapsed line
127
}

Counts

Implementing counts can be done by adding a count field to each node which is the number of nodes in that subtree

The way we maintain this is by setting the count of a node as 1+size(left)+size(right)

Rank

Implementing Rank makes use of these subcounts to determine which sides of a tree to traverse and get the next resulting values in a recursive manner

In Order Traversal

The method for traversing the tree in order is as follows:

Traverse the left subtree
Enqueue current key
Traverse the right subtree

Implementing the above recursively leads to us having an ordered queue of keys

Deletion

To delete we can implement a few different solutions. The lazy approach is to remove the value at a key but then we end up accumulating keys in our table

A more general method for deleting nodes is called Hibbard Deletion

If the node has no children, we just set it’s value as null and propogate the change in counts up
If the node has 1 child, we can replace the parent link with the child
If the node has 2 children, we have to do a few more things:
- Find the next smallest node in the right subtree
- Delete the minimum in the right subtree
- Put the smalest value in the spot of the node we deleted

The problem with the Hibbard deletion process leads to the tree becoming imbalanced over time since we are replacing the right subtree constantly

After a lot of deletes the shape of the tree changes which has a considerable negative impact on the performance of the data structure. This leads to operations on the tree being O(sqrt(N))

2-3 Trees

Generalize BSTs to provide some flexibility in defining performance by using trees that can either have:

2-node: one key, two children
3-node: two keys, three children

Perfect balance: every path from root to end has the same length
Symmetric order: in-order traversal returns keys in ascending order

Searching

Compare search key against keys in node
Find relevant link
- Smaller than both keys = left
- Larget than both keys = right
- Between keys = between link
Follow the relevant link recursively

Insertion

Search for key
Either
- If at 2-node: Replace 2-node with a 3-node
- If at 3-node:
  - Create a temp 4-node
  - Move middle key of 4-node into parent
  - Split remaining into 2 2-nodes
  - Do this recursively up as needed

Splitting nodes is a local transformation and thereby has a constant number of operations

Invariants

Maintain symmetric order and perfect balance
Each transformation should maintain symmetric order and perfect balance

Performance

Since we have perfect balance, every path from the root to the end has the same lenght

Tree height:

Worst case: lg N (all 2-nodes)
Best case: log3 N (all 3 nodes)

Implementation

Implementation of this is possible but it’s quite complicated and there is an easier way to implement this

Left-leaning Red-Black BSTs

Represent a 2-3 tree as a BST
Use internal left-leaning links as 3-nodes

This is a BST such that:

No node has 2 red likns connected to it
Every path from root to link has the same number of black links
Red links lean right

Search

Search is exactly the same as for a BST but is much faster due to the tree remaining balanced

Representation

To represent a red-black BST we use the BST definition we had previously but

Left Rotation

Sometimes when working with a tree we may end up with a right-leaning red link. We may want to update this to rotateLeft instead which can be done as follows:


37 collapsed lines
1
import { BinarySearchTree } from './binary-search-tree'
2
import { Comparison, type Compare } from '../sorting/definition'
3
import type { Key } from './definition'
4

5
type Color = 'red' | 'black'
6

7
class Node<K extends Key, V> {
8
  readonly key: K
9
  val: V
10

11
  /**
12
   * Reference to smaller keys
13
   */
14
  left?: Node<K, V>
15

16
  /**
17
   * Reference to larger keys
18
   */
19
  right?: Node<K, V>
20

21
  /**
22
   * Color of parent link
23
   */
24
  color: Color
25

26
  constructor(key: K, val: V, color: Color) {
27
    this.key = key
28
    this.val = val
29
    this.color = color
30
  }
31
}
32

33
const red = <K extends Key, V>(node?: Node<K, V>): node is (Node<K, V> & { color: 'red' }) => node?.color === 'red'
34

35
export class RedBlackBinarySearchTree<K extends Key, V> extends BinarySearchTree<K, V> {
36
  protected override root?: Node<K, V> = undefined
37

38
  private rotateLeft(h: Node<K, V>) {
39
    const x = h.right
40
    console.assert(red(x))
41

42
    h.right = x.left
43
    x.left = h
44
    x.color = h.color
45
    h.color = 'red'
46

47
    return x
48
  }
53 collapsed lines
49

50
  private rotateRight(h: Node<K, V>) {
51
    const x = h.left
52
    console.assert(red(x))
53

54
    h.left = x.right
55
    x.right = h
56
    x.color = h.color
57
    h.color = 'red'
58

59
    return x
60
  }
61

62
  private flipColors(h: Node<K, V>) {
63
    console.assert(!red(h))
64
    console.assert(red(h.left))
65
    console.assert(red(h.right))
66

67
    h.color = 'red'
68
    h.left.color = 'black'
69
    h.right.color = 'black'
70
  }
71

72
  private redBlackPutAtNode(h: Node<K, V> | undefined, key: K, val: V): Node<K, V> {
73
    if (h === undefined) return new Node(key, val, 'red')
74

75
    if (key < h.key)
76
      h.left = this.redBlackPutAtNode(h.left, key, val)
77
    else if (key > h.key)
78
      h.right = this.redBlackPutAtNode(h.right, key, val)
79
    else if (key === h.key)
80
      h.val = val
81

82

83
    // Lean left
84
    if (red(h.right) && !red(h.left))
85
      h = this.rotateLeft(h)
86

87
    // Balance 4-node
88
    if (red(h.left) && red(h.left?.left))
89
      h = this.rotateRight(h)
90

91
    // Split 4-node
92
    if (red(h.left) && red(h.right))
93
      this.flipColors(h)
94

95
    return h
96
  }
97

98
  public override put(key: K, val: V): void {
99
    this.root = this.redBlackPutAtNode(this.root, key, val)
100
  }
101
}

The important part of the left rotation is that it maintains symmetric order and perfect black balance

Right Rotation

Sometimes to insert a value it is necessary to temporarily rotat a link right, this can also be done as follows:


49 collapsed lines
1
import { BinarySearchTree } from './binary-search-tree'
2
import { Comparison, type Compare } from '../sorting/definition'
3
import type { Key } from './definition'
4

5
type Color = 'red' | 'black'
6

7
class Node<K extends Key, V> {
8
  readonly key: K
9
  val: V
10

11
  /**
12
   * Reference to smaller keys
13
   */
14
  left?: Node<K, V>
15

16
  /**
17
   * Reference to larger keys
18
   */
19
  right?: Node<K, V>
20

21
  /**
22
   * Color of parent link
23
   */
24
  color: Color
25

26
  constructor(key: K, val: V, color: Color) {
27
    this.key = key
28
    this.val = val
29
    this.color = color
30
  }
31
}
32

33
const red = <K extends Key, V>(node?: Node<K, V>): node is (Node<K, V> & { color: 'red' }) => node?.color === 'red'
34

35
export class RedBlackBinarySearchTree<K extends Key, V> extends BinarySearchTree<K, V> {
36
  protected override root?: Node<K, V> = undefined
37

38
  private rotateLeft(h: Node<K, V>) {
39
    const x = h.right
40
    console.assert(red(x))
41

42
    h.right = x.left
43
    x.left = h
44
    x.color = h.color
45
    h.color = 'red'
46

47
    return x
48
  }
49

50
  private rotateRight(h: Node<K, V>) {
51
    const x = h.left
52
    console.assert(red(x))
53

54
    h.left = x.right
55
    x.right = h
56
    x.color = h.color
57
    h.color = 'red'
58

59
    return x
60
  }
41 collapsed lines
61

62
  private flipColors(h: Node<K, V>) {
63
    console.assert(!red(h))
64
    console.assert(red(h.left))
65
    console.assert(red(h.right))
66

67
    h.color = 'red'
68
    h.left.color = 'black'
69
    h.right.color = 'black'
70
  }
71

72
  private redBlackPutAtNode(h: Node<K, V> | undefined, key: K, val: V): Node<K, V> {
73
    if (h === undefined) return new Node(key, val, 'red')
74

75
    if (key < h.key)
76
      h.left = this.redBlackPutAtNode(h.left, key, val)
77
    else if (key > h.key)
78
      h.right = this.redBlackPutAtNode(h.right, key, val)
79
    else if (key === h.key)
80
      h.val = val
81

82

83
    // Lean left
84
    if (red(h.right) && !red(h.left))
85
      h = this.rotateLeft(h)
86

87
    // Balance 4-node
88
    if (red(h.left) && red(h.left?.left))
89
      h = this.rotateRight(h)
90

91
    // Split 4-node
92
    if (red(h.left) && red(h.right))
93
      this.flipColors(h)
94

95
    return h
96
  }
97

98
  public override put(key: K, val: V): void {
99
    this.root = this.redBlackPutAtNode(this.root, key, val)
100
  }
101
}

Flip Colors

When a node has two child links that are both red this represents a 4-node. In order to split a 4-node it is simply necessary to

Convert the parent link to red
Convert the 2 child links to black


61 collapsed lines
1
import { BinarySearchTree } from './binary-search-tree'
2
import { Comparison, type Compare } from '../sorting/definition'
3
import type { Key } from './definition'
4

5
type Color = 'red' | 'black'
6

7
class Node<K extends Key, V> {
8
  readonly key: K
9
  val: V
10

11
  /**
12
   * Reference to smaller keys
13
   */
14
  left?: Node<K, V>
15

16
  /**
17
   * Reference to larger keys
18
   */
19
  right?: Node<K, V>
20

21
  /**
22
   * Color of parent link
23
   */
24
  color: Color
25

26
  constructor(key: K, val: V, color: Color) {
27
    this.key = key
28
    this.val = val
29
    this.color = color
30
  }
31
}
32

33
const red = <K extends Key, V>(node?: Node<K, V>): node is (Node<K, V> & { color: 'red' }) => node?.color === 'red'
34

35
export class RedBlackBinarySearchTree<K extends Key, V> extends BinarySearchTree<K, V> {
36
  protected override root?: Node<K, V> = undefined
37

38
  private rotateLeft(h: Node<K, V>) {
39
    const x = h.right
40
    console.assert(red(x))
41

42
    h.right = x.left
43
    x.left = h
44
    x.color = h.color
45
    h.color = 'red'
46

47
    return x
48
  }
49

50
  private rotateRight(h: Node<K, V>) {
51
    const x = h.left
52
    console.assert(red(x))
53

54
    h.left = x.right
55
    x.right = h
56
    x.color = h.color
57
    h.color = 'red'
58

59
    return x
60
  }
61

62
  private flipColors(h: Node<K, V>) {
63
    console.assert(!red(h))
64
    console.assert(red(h.left))
65
    console.assert(red(h.right))
66

67
    h.color = 'red'
68
    h.left.color = 'black'
69
    h.right.color = 'black'
70
  }
31 collapsed lines
71

72
  private redBlackPutAtNode(h: Node<K, V> | undefined, key: K, val: V): Node<K, V> {
73
    if (h === undefined) return new Node(key, val, 'red')
74

75
    if (key < h.key)
76
      h.left = this.redBlackPutAtNode(h.left, key, val)
77
    else if (key > h.key)
78
      h.right = this.redBlackPutAtNode(h.right, key, val)
79
    else if (key === h.key)
80
      h.val = val
81

82

83
    // Lean left
84
    if (red(h.right) && !red(h.left))
85
      h = this.rotateLeft(h)
86

87
    // Balance 4-node
88
    if (red(h.left) && red(h.left?.left))
89
      h = this.rotateRight(h)
90

91
    // Split 4-node
92
    if (red(h.left) && red(h.right))
93
      this.flipColors(h)
94

95
    return h
96
  }
97

98
  public override put(key: K, val: V): void {
99
    this.root = this.redBlackPutAtNode(this.root, key, val)
100
  }
101
}

Insertion

When inserting we want to maintain the 2-3 accordance.

Case 1 - insert into a 2-node at the bottom
- Do a normal BST insert, color new link red
- If new red link is right, rotate it left
Case 2 - Insert into a tree with exactly 2 nodes
- Do a normal BST insert, color new link red
- Rotate to balance 4 node if needed
- Flip colors to pass red link up one level
- Rotate to make lean left if needed
- Repeat case 1 or 2 up the tree if needed


71 collapsed lines
1
import { BinarySearchTree } from './binary-search-tree'
2
import { Comparison, type Compare } from '../sorting/definition'
3
import type { Key } from './definition'
4

5
type Color = 'red' | 'black'
6

7
class Node<K extends Key, V> {
8
  readonly key: K
9
  val: V
10

11
  /**
12
   * Reference to smaller keys
13
   */
14
  left?: Node<K, V>
15

16
  /**
17
   * Reference to larger keys
18
   */
19
  right?: Node<K, V>
20

21
  /**
22
   * Color of parent link
23
   */
24
  color: Color
25

26
  constructor(key: K, val: V, color: Color) {
27
    this.key = key
28
    this.val = val
29
    this.color = color
30
  }
31
}
32

33
const red = <K extends Key, V>(node?: Node<K, V>): node is (Node<K, V> & { color: 'red' }) => node?.color === 'red'
34

35
export class RedBlackBinarySearchTree<K extends Key, V> extends BinarySearchTree<K, V> {
36
  protected override root?: Node<K, V> = undefined
37

38
  private rotateLeft(h: Node<K, V>) {
39
    const x = h.right
40
    console.assert(red(x))
41

42
    h.right = x.left
43
    x.left = h
44
    x.color = h.color
45
    h.color = 'red'
46

47
    return x
48
  }
49

50
  private rotateRight(h: Node<K, V>) {
51
    const x = h.left
52
    console.assert(red(x))
53

54
    h.left = x.right
55
    x.right = h
56
    x.color = h.color
57
    h.color = 'red'
58

59
    return x
60
  }
61

62
  private flipColors(h: Node<K, V>) {
63
    console.assert(!red(h))
64
    console.assert(red(h.left))
65
    console.assert(red(h.right))
66

67
    h.color = 'red'
68
    h.left.color = 'black'
69
    h.right.color = 'black'
70
  }
71

72
  private redBlackPutAtNode(h: Node<K, V> | undefined, key: K, val: V): Node<K, V> {
73
    if (h === undefined) return new Node(key, val, 'red')
74

75
    if (key < h.key)
76
      h.left = this.redBlackPutAtNode(h.left, key, val)
77
    else if (key > h.key)
78
      h.right = this.redBlackPutAtNode(h.right, key, val)
79
    else if (key === h.key)
80
      h.val = val
81

82

83
    // Lean left
84
    if (red(h.right) && !red(h.left))
85
      h = this.rotateLeft(h)
86

87
    // Balance 4-node
88
    if (red(h.left) && red(h.left?.left))
89
      h = this.rotateRight(h)
90

91
    // Split 4-node
92
    if (red(h.left) && red(h.right))
93
      this.flipColors(h)
94

95
    return h
96
  }
97

98
  public override put(key: K, val: V): void {
99
    this.root = this.redBlackPutAtNode(this.root, key, val)
100
  }
1 collapsed line
101
}

Performance

Lerft leaning red-black trees will approach lg 2 N hehght, in the worst case it will be 2 lg N

B Trees

Given some contstraints such as a file system, we have the following:

Locate a page - slow
Read a page - fast

We want to optimize in order to minimize the number of propbes that need to be done in order to locate a page

B-trees generalize 2-3 trees by allowing up to M-1 key-link pairs per node where M is as large as possible for the given usecase

At least 2 key-link paris at root
At least M/2 key-link paris in other nodex
External nodes contain client keys
Internal nodes contain copies of keys to guide search

In practive, the number of probes in a B-tree is at most 4, an optimization that’s possible is to keep the root page in memory at all times

Performance Overview

Implementation	Guarantee			Average			Ordered Iteration
	search	insert	delete	search	insert	delete
Sequential Search (Linked List)	N	N	N	N/2	N	N/2	no
Binary Search (Ordered Array)	lg N	N	N	lg N	N/2	N/2	yes
BST	N	N	N	1.39 lg N	1.39 lg N	sqrt(N)	yes
2-3 Tree	c lg N	c lg N	c lg N	c lg N	c lg N	c lg N	yes
Left Leaning Red-Black Tree	2 lg N	2 lg N	2 lg N	lg N	lg N	lg N	yes

Sets

Basically just a set without anything to do with value

add(key)
contains(key)
remove(key)
size
iterator

Indexing

File indexing: Build a Symbol Table with key as some search term, and value as a Set<File>
Concordance indexing: Build a Symbol Table with key and value as Set<Integer> where we reference the position in the array where a given key occurs

Sparse Vectors/Matrices

In many usecases we have matrices with very few non-zero values and very large sizes, we can take advantage of these by using Symbol tables to only store the keys and values, otherwise we can assume a 0

In the case of a vector, we can use a Symbol Table such that SparseVector == ST<Integer, Float>

In the case of a matrix we can use the definition of a Sparse Vector such that SparseMatrix == ST<Integer, SparseVector> == ST<Integer, ST<Integer, Float>