Symbol Tables

Updated: 18 April 2024

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
  private 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
  private 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
  private 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
  private 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 of 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