Python Code

Symbol Table API
A Symbol Table is a collection of key-value pairs, where the key is the Symbol.
1.1) Date.py is an example of an user-created immutable type which can be used as a key
1.2) Client for ST.py: FrequencyCounter.py
Elementary Symbol Table Implementations
2.1) SequentialSearchST.py, an unordered linked-list
2.2) BinarySearchST.py, ordered array. Fast lookup (slow insert)
Ordered Operations: get, put, delete, size, min, max, floor, ceiling, rank, etc.
3.1) ST.py
Binary Search Trees A binary tree in symmetric order
A classic data structure that enables us to provide efficient implementations of Symbol Table algorithms
4.1) BST.py
Ordered Operations in BSTs
Deletion in BSTs

Table of Contents for Examples

EX1 Order of "put"s determine tree shape

Examples

EX1 Order of "put"s determine tree shape

14:30 There are many different BSTs that correspond to the same set of keys.
The number of compares depends on the order in which the keys come in.



In [1]:

    
# Setup for running examples
import sys
import os
sys.path.insert(0, '{GIT}/PrincetonAlgorithms/py'.format(GIT=os.environ['GIT']))
from AlgsSedgewickWayne.BST import BST

# Function to convert keys to key-value pairs where
#   1. the key is the letter and
#   2. the value is the index into the key list
get_kv = lambda keys: [(k, v) for v, k in enumerate(keys)]

Tree shape: Best case



In [2]:

    
# All of these will create the same best case tree shape 
# Each example has the same keys, but different values
BST(get_kv(['H', 'C', 'S', 'A', 'E', 'R', 'X'])).wr_png("BST_bc0.png")
BST(get_kv(['H', 'S', 'X', 'R', 'C', 'E', 'A'])).wr_png("BST_bc1.png")
BST(get_kv(['H', 'C', 'A', 'E', 'S', 'R', 'X'])).wr_png("BST_bc2.png")









    



  wrote: BST_bc0.png
  wrote: BST_bc1.png
  wrote: BST_bc2.png

Best Case Tree Shape

Tree shape: Worst case



In [3]:

    
# These will create worst case tree shapes
BST(get_kv(['A', 'C', 'E', 'H', 'R', 'S', 'X'])).wr_png("BST_wc_fwd.png")
BST(get_kv(['X', 'S', 'R', 'H', 'E', 'C', 'A'])).wr_png("BST_wc_rev.png")









    



  wrote: BST_wc_fwd.png
  wrote: BST_wc_rev.png

Worst Case Tree Shape

Incrementing Order: A C E H R S X	Decrementing Order: X S R H E C A

Elementary Symbol Tables

Python Code

Table of Contents for Examples

Examples

EX1 Order of "put"s determine tree shape

Tree shape: Best case

Best Case Tree Shape

Tree shape: Worst case

Worst Case Tree Shape