Week 17 - Dictionaries, Binary Trees, Self Balancing Trees Flashcards
Dictionary
An ADT with operations insert, delete and find. Each entry in a dictionary is made up of key-value pair.
Key-value pairs
A pair of items made up of a key and value. They key and value are associated with each other – the key is a unique identifier used to retrieve the associated value and is typically a string or number. The value is the data or information stored under the key.
Dictionary operations
void insert(Key k, Value v): stores an entry with the key-value pair (k, v). Returns an error if k is already in the dictionary.
void delete(Key k): deletes the entry associated with the key k from the dictionary. Returns an error if k does not exist.
Value find(Key k): determines whether there is an entry in the dictionary associated with key k. If there ism return the associated value, else return null reference.
Sequential allocation for storing key-value pairs in a dictionary
Store the entries in a linear array without sorting.
Takes O(n) time complexity to find key-value pair.
Takes O(1) time complexity to insert a new key-value pair, assuming there is space in the array. Checking for duplicates takes O(n) time complexity.
Sorted allocation for storing key-value pairs in a dictionary
Store the entries in an array sorted by the key value.
Takes O(log n) time complexity to find a key-value pair and to complete a binary search.
Takes O(n) time complexity to insert or delete entries as elements in array must be moved around to make space.
Binary tree
A tree that has at most 2 children per node – a left and right child.
Unlike in regular trees, even if both parent and child nodes are the same for 2 trees, if the child is the left node on one tree and the right tree on another, the two trees are not the same.
Binary search tree
A binary tree where each node has a key-value pair and nodes are “sorted” by their keys.
The nodes are sorted if for every node, its key is >= all keys in its left subtree and its key is < all keys in its right subtree.
Balanced binary search tree
A BST where the height of the tree is kept as small as possible.
Causes much more efficient searching, insertion and deletion than an unbalanced/ degenerate BST.
Unbalanced binary search tree
A BST where the difference in height in the left and right subtrees of the root is more than 1.
Degenerate binary search tree
A BST where each parent node has only one child. Causes the tree to resemble a linked list more than a tree. Causes inefficient operations such as searching, insertion and deletion.
Best and worst case height of a BST
Ω(log n) - a balanced tree
O(n) - a degenerate tree
BST ADT Find
If root has key, return root,
Else if key smaller, go left,
Else, go right.
Time complexity of find
For a BST of height h, the worst case time complexBSTity of find() is O(h)
BST ADT Insert
If the BST has no root, make new node the root.
Else, traverse the tree, moving to the left child if newNode<parent>parent, until there is no child to traverse to. At this point, add the newNode to this position in the tree.</parent>
How does order of insertion matter
Order of insertion can affect the tree and make it more or less efficient if the order makes the tree balanced/unbalanced.
Time complexity of insertion
For a BST of height h, worst case time complexity of insert() is O(h). However, this depends on insertion order.
If insertion order is random then expected height is O(log n) meaning average time complexity of insert() is O(log n).
More complex insertions that balance the BST height at O(log n) improve time complexity of insert().
BST ADT Delete
Find node to be deleted
- If node is a leaf, remove the node from the tree by removing the it as the child of its parent node.
- If the node has 1 child, the child replaces the deleted node.
- If the node has 2 children, inspect the right subtree of the node to be delete, find the minimum value of this subtree (the successor) and replace the node to be deleted with this node.
Non-binary search trees
A search tree where a node can have more than 2 children.
A node in a non-binary search tree can have multiple keys.
Self-balancing search tree
A search tree that will automatically maintain a balanced structure by keeping height is as small as possible.
This ensures that search, insertion and deletion operations are as efficient as possible.
Examples of self balancing trees
- 2-3 trees: tertiary self-balancing search trees
- AVL trees: self-balancing BST
- Red-black trees are a (BST) generalization of 2-3 trees
- B-trees: generalization of 2-3 trees to more keys per node
Self balancing and height balancing
Some trees are self-balancing but not height-balanced.
Self-balancing will always balance the tree to achieve O(log n) by rotating and re-ordering the tree
Height balanced trees only changes the tree if the difference in height of the left and right subtrees from the node is greater than 1. This does not mean the tree will always have time complexity of O(log n) for operations.
2-3 Trees
A 2-3 tree is a self-balancing search tree where each node can have 2-nodes (1 key, 2 children) or 3-nodes (2 keys, 3 children).
A 2-3 search tree will always be perfectly balanced - every path from the root to a leaf has the same length.
Existing nodes are moved around when a new node is inserted to maintain perfect balance in the tree.
