Trees, Sets, Dictionaries, and MultiDictionaries
Data Structures Part 2
Binary Tree - Vocab
Root
Parent
Child (Left / Right)
Sibling
Grandparent/child
Uncle / Aunt
Cousin
Leaf Node
Internal Node
Path
Height
Complete
Full
Binary Search Tree (BST)
BST Operations
Where would you add the number 2?
Where would you add the number 4?
How would you find the value 13?
Why is this called a Binary Search Tree?
BST Remove
BST Remove
What if you wanted to remove 2?
BST Remove
Inorder Successor / Predecessor
Transversals
Level Order (Usually implemented using a Queue!)
Pre Order: (root, left, right)
In Order (left, root, right)
Post Order: (left, right, root)
Fun BST Questions
1) How can you organize the data in a BST so it is the most efficient? So it is the least efficient?
2) How many different ways can a data set of n values be organized in a BST?
Set
Dictionary
MultiDictionary
Dictionary where each key associates with multiple values
Adding values does not remove old values