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:
1export type Key = string | number2
3export interface SymbolTable<K extends Key, V> {4 /**5 * Put a value at a given key6 */7 put(key: K, value: V): void8
9 /**10 * Get a value given a key11 */12 get(key: K): V | undefined13
14 /**15 * Delete the value with the given key16 */17 delete(key: K): void18
19 /**20 * Check if the key/value exists in the symbol table21 */22 contains(key: K): boolean23
24 /**25 * Check if the symbol table is empty26 */27 isEmpty(): boolean28
29 /**30 * Get the total number of key value pairs in the symbol table31 */32 size(): number33
34 /**35 * Iterate through all keys in the table36 */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
andx == z
thenx == 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
1export type Key = string | number2
3export interface SymbolTable<K extends Key, V> {4 /**5 * Put a value at a given key6 */7 put(key: K, value: V): void8
9 /**10 * Get a value given a key11 */12 get(key: K): V | undefined13
14 /**15 * Delete the value with the given key16 */17 delete(key: K): void18
19 /**20 * Check if the key/value exists in the symbol table21 */22 contains(key: K): boolean23
24 /**25 * Check if the symbol table is empty26 */27 isEmpty(): boolean28
29 /**30 * Get the total number of key value pairs in the symbol table31 */32 size(): number33
34 /**35 * Iterate through all keys in the table36 */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
1import { Comparison, type Compare } from '../sorting/definition'2import type { Key } from './definition'3
4class Node<K extends Key, V> {5 readonly key: K6 val: V7
8 /**9 * Reference to smaller keys10 */11 left?: Node<K, V>12
13 /**14 * Reference to larger keys15 */16 right?: Node<K, V>17
18 constructor(key: K, val: V) {19 this.key = key20 this.val = val21 }22}23
24export 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 = compare31 }32
33 public get(key: K): V | undefined {34 let x: Node<K, V> = this.root35
36 while (x !== undefined) {37 const cmp = this.compare(key, x.key)38
39 if (cmp === Comparison.Less) x = x.left40 else if (cmp === Comparison.Greater) x = x.right41 else return x.val42 }43
44 return undefined45 }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 = val60
61 return x62 }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.root70 while (x.right) x = x.right71
72 return x.key73 }74
75 public min(): K | undefined {76 let x = this.root77 while (x.left) x = x.left78
79 return x.key80 }81
82 private floorOfNode(83 x: Node<K, V> | undefined,84 key: K,85 ): Node<K, V> | undefined {86 if (x === undefined) {87 return undefined88 }89
90 const cmp = this.compare(key, x.key)91 if (cmp === Comparison.Equal) return x92
93 if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)94
95 const t = this.floorOfNode(x.right, key)96 if (t) return t97 else return x98 }99
100 public floor(key: K): K | undefined {101 const x = this.floorOfNode(this.root, key)102 return x?.key103 }104
105 private ceilOfNode(106 x: Node<K, V> | undefined,107 key: K,108 ): Node<K, V> | undefined {109 if (x === undefined) {110 return undefined111 }112
113 const cmp = this.compare(key, x.key)114 if (cmp === Comparison.Equal) return x115
116 if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)117
118 const t = this.ceilOfNode(x.left, key)119 if (t) return t120 else return x121 }122
123 public ceil(key: K): K | undefined {124 const x = this.ceilOfNode(this.root, key)125 return x?.key126 }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
1import { Comparison, type Compare } from '../sorting/definition'2import type { Key } from './definition'3
4class Node<K extends Key, V> {5 readonly key: K6 val: V7
8 /**9 * Reference to smaller keys10 */11 left?: Node<K, V>12
13 /**14 * Reference to larger keys15 */16 right?: Node<K, V>17
18 constructor(key: K, val: V) {19 this.key = key20 this.val = val21 }22}23
24export 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 = compare31 }32
33 public get(key: K): V | undefined {34 let x: Node<K, V> = this.root35
36 while (x !== undefined) {37 const cmp = this.compare(key, x.key)38
39 if (cmp === Comparison.Less) x = x.left40 else if (cmp === Comparison.Greater) x = x.right41 else return x.val42 }43
44 return undefined45 }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 = val60
61 return x62 }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.root70 while (x.right) x = x.right71
72 return x.key73 }74
75 public min(): K | undefined {76 let x = this.root77 while (x.left) x = x.left78
79 return x.key80 }81
82 private floorOfNode(83 x: Node<K, V> | undefined,84 key: K,85 ): Node<K, V> | undefined {86 if (x === undefined) {87 return undefined88 }89
90 const cmp = this.compare(key, x.key)91 if (cmp === Comparison.Equal) return x92
93 if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)94
95 const t = this.floorOfNode(x.right, key)96 if (t) return t97 else return x98 }99
100 public floor(key: K): K | undefined {101 const x = this.floorOfNode(this.root, key)102 return x?.key103 }104
105 private ceilOfNode(106 x: Node<K, V> | undefined,107 key: K,108 ): Node<K, V> | undefined {109 if (x === undefined) {110 return undefined111 }112
113 const cmp = this.compare(key, x.key)114 if (cmp === Comparison.Equal) return x115
116 if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)117
118 const t = this.ceilOfNode(x.left, key)119 if (t) return t120 else return x121 }122
123 public ceil(key: K): K | undefined {124 const x = this.ceilOfNode(this.root, key)125 return x?.key126 }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
1import { Comparison, type Compare } from '../sorting/definition'2import type { Key } from './definition'3
4class Node<K extends Key, V> {5 readonly key: K6 val: V7
8 /**9 * Reference to smaller keys10 */11 left?: Node<K, V>12
13 /**14 * Reference to larger keys15 */16 right?: Node<K, V>17
18 constructor(key: K, val: V) {19 this.key = key20 this.val = val21 }22}23
24export 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 = compare31 }32
33 public get(key: K): V | undefined {34 let x: Node<K, V> = this.root35
36 while (x !== undefined) {37 const cmp = this.compare(key, x.key)38
39 if (cmp === Comparison.Less) x = x.left40 else if (cmp === Comparison.Greater) x = x.right41 else return x.val42 }43
44 return undefined45 }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 = val60
61 return x62 }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.root70 while (x.right) x = x.right71
72 return x.key73 }74
75 public min(): K | undefined {76 let x = this.root77 while (x.left) x = x.left78
79 return x.key80 }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 undefined88 }89
90 const cmp = this.compare(key, x.key)91 if (cmp === Comparison.Equal) return x92
93 if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)94
95 const t = this.floorOfNode(x.right, key)96 if (t) return t97 else return x98 }99
100 public floor(key: K): K | undefined {101 const x = this.floorOfNode(this.root, key)102 return x?.key103 }104
105 private ceilOfNode(106 x: Node<K, V> | undefined,107 key: K,108 ): Node<K, V> | undefined {109 if (x === undefined) {110 return undefined111 }112
113 const cmp = this.compare(key, x.key)114 if (cmp === Comparison.Equal) return x115
116 if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)117
118 const t = this.ceilOfNode(x.left, key)119 if (t) return t120 else return x121 }122
123 public ceil(key: K): K | undefined {124 const x = this.ceilOfNode(this.root, key)125 return x?.key126 }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
1import { Comparison, type Compare } from '../sorting/definition'2import type { Key } from './definition'3
4class Node<K extends Key, V> {5 readonly key: K6 val: V7
8 /**9 * Reference to smaller keys10 */11 left?: Node<K, V>12
13 /**14 * Reference to larger keys15 */16 right?: Node<K, V>17
18 constructor(key: K, val: V) {19 this.key = key20 this.val = val21 }22}23
24export 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 = compare31 }32
33 public get(key: K): V | undefined {34 let x: Node<K, V> = this.root35
36 while (x !== undefined) {37 const cmp = this.compare(key, x.key)38
39 if (cmp === Comparison.Less) x = x.left40 else if (cmp === Comparison.Greater) x = x.right41 else return x.val42 }43
44 return undefined45 }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 = val60
61 return x62 }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.root70 while (x.right) x = x.right71
72 return x.key73 }74
75 public min(): K | undefined {76 let x = this.root77 while (x.left) x = x.left78
79 return x.key80 }81
82 private floorOfNode(83 x: Node<K, V> | undefined,84 key: K,85 ): Node<K, V> | undefined {86 if (x === undefined) {87 return undefined88 }89
90 const cmp = this.compare(key, x.key)91 if (cmp === Comparison.Equal) return x92
93 if (cmp === Comparison.Less) return this.floorOfNode(x.left, key)94
95 const t = this.floorOfNode(x.right, key)96 if (t) return t97 else return x98 }99
100 public floor(key: K): K | undefined {101 const x = this.floorOfNode(this.root, key)102 return x?.key103 }104
105 private ceilOfNode(106 x: Node<K, V> | undefined,107 key: K,108 ): Node<K, V> | undefined {109 if (x === undefined) {110 return undefined111 }112
113 const cmp = this.compare(key, x.key)114 if (cmp === Comparison.Equal) return x115
116 if (cmp === Comparison.Greater) return this.ceilOfNode(x.right, key)117
118 const t = this.ceilOfNode(x.left, key)119 if (t) return t120 else return x121 }122
123 public ceil(key: K): K | undefined {124 const x = this.ceilOfNode(this.root, key)125 return x?.key126 }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