CS 234 Module 7: Dictionaries

ADT Dictionary

Supports (key, element) pairs accessed by key, where:

• Keys are distinct but not necessarily orderable

• Elements are general data

ADD(D, Key, Element)

Adds a new pair (Key, Element); replaces a pair with Key if any

LOOK_UP(D, Key)

Returns the element in pair (Key, element) if any, else False

Dictionary Contiguous Implementation

Data structures:

• Array

• Variable First

Definition:

• Data items are stored contiguously, starting at index 0.

• Each array entry contains an ADT Pair storing a key and an element.

• First stores the index of the first empty slot.

Dictionary Linked Implementation

Data structures:

• Variable Head storing the null pointer or a pointer to a linked list of nodes, each storing a key, an element, and a pointer to the next node in the list, if any, and otherwise the null pointer

Definition:

• If Head stores the null pointer, the ADT is empty.

• Each linked node stores a data item.

In various ADT implementations, what does the cost of operations usually depends on?

The cost of searching.

Ordered Array

An array in which data items appear in sorted order

Ordered Linked List

A linked list in which data items appear in sorted order

Dictionary Ordered Contiguous Implementation

Data structures:

• Array

• Variable First

Definition:

• Data items are stored contiguously, starting at slot 0.

• For any slots i and j in the array, the key of the data item in slot i is less than the key of the data item in position j.

• Each slot stores an ADT Pair containing a key and an element.

• First stores the index of the first empty slot.

Select each choice that has a running time that is faster for linear search in an ordered array than for linear search in an unordered array.

Best case for unsuccessful search

Binary Search

A method of searching in a nondecreasing sequence of numbers

Algorithm for ADD(D, Key, Element) under Dictionary Ordered Contiguous Implementation

• If the Key is in D:

  1. Binary search of slots until a Pair with key Key is found

  2. Updates the element in Pair to Element

• If the Key is not found in D:

  1. Binary search of slots until the slot Slot where Key should belong

  2. Creates a new ADT Pair New containing Key and Element

  3. Move the data item stored in slot i to slot i+1 for i from Slot to the last slot storing a data item

  4. Inserts New in slot Slot

  5. Update First to First + 1

Worst-case running time of ADD(D, Key, Element) and DELETE(D, Key) under Dictionary Ordered Contiguous Implementation

θ(n) since data items need to be shifted

Worst-case running time of binary search

θ(log n)

Algorithm for Delete(D, Key) under Dictionary Ordered Contiguous Implementation

1. Binary search of slots until an ADT Pair Pair that contains key Key

2. Inserts the data item stored in slot i into slot i-1 for i from slot+1 to the last slot storing a data item

3. Rewrites slot First -1 to empty

4. Updates First to First -1

Dictionary Ordered Linked Implementation

Data structures:

• Variable Head storing the null pointer or a pointer to a linked list of nodes, each storing a key, an element, and a pointer to the next node in the list, if any, and otherwise the null pointer

Definition:

• If Head stores the null pointer, the ADT is empty.

• For any positions i and j in the linked list, the key of the data item in position i is less than the key of the data item in position j.

Algorithm for ADD(D, Key, Element) under Dictionary Ordered Linked Implementation

1. Linear Search of linked nodes until the linked node Node storing a pair Pair containing Key, or a pair containing a key greater than Key, or the last linked node is read

2. Updates the element in Pair to Element if found.

   • Otherwise, allocates a new linked node New storing an ADT Pair containing Key and Element and adds New before Node in the list

   • Or add New after the final node in the list, if Key > final node’s key or D is empty.

Algorithm for DELETE(D, Key) under Dictionary Ordered Linked Implementation

1. Linear search of linked nodes until a linked node Node storing an ADT Pair containing the key Key is found

2. Removes that linked node Node

Worst-case running time of ADD(D, Key, Element) and DELETE(D, Key) under Dictionary Ordered Linked Implementation

θ(n)

Asymptotically the same

Describing two functions that are in θ(⨍(n)) for the same function ⨍(n)

What is the worst-case cost of the algorithm for creating an ADT Dictionary filled with n data items?

The algorithm consists of one use of CREATE() and one use of ADD() for each data item.
The cost of ADD() is θ(k), where k is the number of data items in the dictionary at the time of the operation.

We can view ADD() operation as the loop body, where the cost of each iteration grows linearly with the iteration number. So the runtime is θ(n²)

Stable Sorting Algorithm

Sorting algorithms where equal-valued items are in the same order before and after sorting.

ADD_ALL(D, Items)

Adds data items in Items to Dictionary D by inserting items into (list/slots) in order

Worst-case runtime of ADD_ALL(D, Items)

θ(n)

Binary Search Tree (BST)

For every node N in the tree, where K is the key stored in the node:

• The key values stored in the left subtree of N are less than K

  • The key values stored in the right subtree of N are greater than K

Dictionary Binary Search Tree Implementation

Data structures:

• Binary search tree

Definition:

• Each node stores a (key, element) pair

LOOK_UP(D, Key) in BST

• If the key being sought is equal to the key stored in the node, we stop and return the element in the node.

• If the key being sought is smaller than the key stored in the node, we continue the search at the left child of the node, if any, and otherwise stop and return False.

• If the key being sought is larger than the key stored in the node, we continue the search at the right child of the node, if any, and otherwise stop and return False.

ADD(D, Key, Element) in BST

1. Search a node storing a pair with Key

2. If it finds a node, it replaces the element in that node

3. If it doesn’t, it will find where the new node should be placed by “falling off” the tree and creating a new leaf

DELETE(D, Key) in BST: Case 1

• Searches for the node Node storing Key.

• If Node has no children, deletes Node.

DELETE(D, Key) in BST: Case 2

• Searches for the node Node storing Key.

• If Node has only one child Child:

  • Determines whether Node is a left or right child.

  • If Node is a left child, makes the child of Node into the left child of the parent of Node.

  • If Node is a right child, makes the child of Node into the right child of the parent of Node.

Binary Search Tree Property

For every node, the values in the left subtree are smaller (or equal) and the values in the right subtree are larger (or equal)

DELETE(D, Key) in BST: Case 3

• Searches for the node Node storing Key.

• If Node has two children:

  • Finds the inorder successor Succ of Node.

  • Swaps Node's (key, element) pair with Succ's (key, element) pair.

  • Deletes Succ using Case 1 or 2.

Dictionary Binary Search Tree as ADT Binary Tree implementation

Data structures:

• Binary search tree

Definition:

• Each node stores a (key, element) pair.

• The binary search tree is implemented as an augmented ADT Binary Tree.

Functionality of Augmented ADT Binary Tree

• Storing and accessing keys and elements at each node

• Determining if a node is a left or a right child

• Moving a subtree to a new parent

• Swapping values stored in nodes

SET_VALUE(B, Node, Key, Element)

Updates value in Node to (Key, Element)

ADD_LEAF(B, Par, Side, Key Element)

1. If Par and Side are both empty

   • Adds a node with value (Key, Element) as the root of B, replacing all nodes in B

2. If Par is a node in B, and Side is Left or Right

   • Adds a node with value (Key, Element) as the Side child of Par, replacing all nodes in the Side subtree of Par, if any

KEY(B, Node)

Produces the key in Node

Element(B, Node)

Produces the element in Node

Side(B, Node)

Produces Left if Node is a left child, Right if Node is a right child

MODIFY_LINK(B, Old_Par, Old_Side, New_Par, New_Side, Node)

Replaces New_Side child of New_Par, if any by Node

SWAP_NODE_VALUES(B, One, Two)

Swaps values in One and Two

LOOK_UP(D, Key) Algorithm

• Uses ROOT to start at the root.

• Repeatedly:

  • Uses Key to extract the key in the current node.

  • Compares the value being searched to the key in the current node.

  • Uses LEFT_CHILD or RIGHT_CHILD to update the current node.

• If a match is found, uses ELEMENT to extract the element.

• Returns element if found and False otherwise.

ADD(D, Key, Element)

• Searches for a node storing Key.

• For successful search, uses SET_VALUE to replace the current element with ELEMENT.

• For unsuccessful search, uses SIDE to determine the side to use in ADD_LEAF.

DELETE(D, Key) Algorithm

• Searches for the node Node storing Key.

• For Case 1, uses DELETE_LEAF.

• For Case 2, uses SIDE and MODIFY_LINK.

• For Case 3, finds the inorder successor or inorder predecessor and uses SWAP_NODE_VALUES.

What is the worst-case cost of finding the inorder successor or predecessor of a node?

Linear in the height of the tree

How to prove that the inorder successor has no left child?

Let Succ be the inorder successor of a Node storing Key, Bigger be the key of Succ, and Node has a right child:

• Key < Bigger

• There is no key with a value between Key and Bigger

• The node Succ is in the right subtree of the Node

The key of the left child of Succ has to be larger than key, but smaller than Bigger. This contradicts with the fact that there is no key between Key and Bigger

How to prove that the inorder predecessor has no right child?

Let Pred be the inorder predecessor of a Node storing Key, Smaller be the key of Pred, and Node has a left child:

• Smaller < Key

• There is no key with a value between Smaller and Key

• The node Pred is in the left subtree of the Node

The key of the right child of Pred has to be smaller than Key, but larger than Smaller. This contradicts the fact that there is no key between Smaller and Key

What is the height of a perfect tree?

Logarithmic in the number of nodes

Perfect Binary Tree

A binary tree in which each node has zero or two children and all leaves are at the same depth

Complete Binary Tree

A binary tree in which every level, except possibly the last, is completely filled, and all nodes on the last level are as far left as possible

What is the height of a complete binary tree?

Logarithmic in the number of nodes

What is the tradeoff in the degree of organization of data (e.g. Perfect Tree → Complete Binary Tree)

• Organizing the data more might lower the cost of search.

• Organizing the data less might lower the cost of modification.

Balanced Node

A node where the difference of its left and right subtree is at most 1.

Imbalanced Node

A node where the difference of its left and right subtree is more than 1.

Height-Balance Property

Satisfied by any tree where every node is balanced

AVL Tree

A height-balanced BST that satisfies both the binary search tree property and height-balance property

What is the height of an AVL tree with n nodes?

It has height θ(log n) (aka logarithmic height)

Pivot Node

The lowest imbalanced node in the tree after an insertion or deletion

Rotation on Pivot Node

A rearrangement of subtrees that rebalances the tree without violating binary search order.

Dictionary AVL Tree Implementation

Data structures:

• AVL tree

Definition:

• Each node stores a (key, element) pair.

ADD(D, Key, Element) Algorithm in Dictionary AVL Tree Implementation

1. ADD(D, Key, Element) Algorithm in Dictionary AVL Tree ImplementationSearches for a node storing Key.

2. For successful search, replaces the element in the node with Element.

3. For unsuccessful search, creates a new node storing Key and Element and adds it in a new leaf Leaf.

4. Visits the path from Leaf to the root, updating heights and checking balance.

5. If an imbalanced node is discovered, executes a rotation.

DELETE(D, Key) Algorithm in Dictionary AVL Tree Implementation

1. Searches for the node storing Key.

2. Deletes the node as in a BST.

3. Visits the path from the deleted node to the root, updating heights and checking balance.

4. If an imbalanced node is discovered, executes a rotation.

5. Continues tracing the path to the root, updating heights and checking balance, pivoting again as often as needed.

HEIGHT(B, Node)

Returns the value of height field of Node

SET_HEIGHT(B, Node, Height)

Updates the value of height field of Node to Height

What are the goals of rotation

• Restore the height-balance property

• Preserve the binary search tree property

• Change a constant number of pointers

Cases for Rotations

Case	Which subtree of the pivot is higher?	What are the relative heights of the subtrees of the higher subtree of the pivot?
1	Left subtree is higher	Left subtree is higher
2	Left subtree is higher	Right subtree is higher
3	Left subtree is higher	Both subtrees have equal height
4	Right subtree is higher	Right subtree is higher
5	Right subtree is higher	Left subtree is higher
6	Right subtree is higher	Both subtrees have equal height

The cases can be grouped into: Case 1 & 4, Case 2 & 5, and Case 3 & 6

AVL Tree Rotation Case 1 (and 4)

Higher pivot subtree = Left
Higher subtree of the higher pivot subtree = Left

Height of subtree:

• After modification: h+3

• After rotation: h+2

How to choose the new root for AVL Tree rotation?

We choose a child or a child of a child of the pivot node to be the new root

AVL Tree Rotation Case 2 (and 5)

Higher pivot subtree = Left
Higher subtree of the higher pivot subtree = Right

Height of subtree:

• After modification: h+3

• After rotation: h+2

AVL Tree Rotation Case 3 (and 6)

Higher pivot subtree = Left
Higher subtree of the higher pivot subtree = Equal

Height of subtree:

• After modification: h+3

• After rotation: h+3

What do we denote as the height of a empty tree?

-1

Analysis for ADD() in AVL Trees

• Cases 3 and 6 cannot happen, as adding one node cannot result in two subtrees getting too tall.

• In all remaining cases, height of subtree goes from (too tall due to addition) to .

• After one rotation, the rest of the tree is fixed.

Analysis for DELETE() in AVL Trees

• In Cases 3 and 6, the height before deletion and the height after rotation are the same.

• In the other cases, the height before deletion is greater than the height after rotation.

• After one rotation, more rotations might be required.

Multiway Search Tree

A search tree with nodes that have two or more children, where d is the number of ranges

What is the best worst-case cost of search for a tree with a split into up to d ranges at each node?

A tree with d children at each node will have height θ(log_d n)

(2,3) Tree

• Each internal node has either:

  • 1 key and 2 children

  • 2 keys and 3 children

• All leaves are at the same depth and have 1 or 2 keys

• Keys in the left subtree are smaller than the first or only key,

• Keys in the middle subtree (if any) are between the first and second keys

• Keys in the right subtree are greater than the second or only key

What is the height of a (2,3) tree storing n data items?

It has a height of θ(n)

Dictionary (2,3) Tree Implementation

Data structures:

• (2,3) tree

Definition:

• Each node stores one or two (key, element) pairs.

ADD(D, Key, Element) in (2,3) Tree

• If the tree already contains a pair with the search key, simply update the element

• If it doesn’t, search until it leads us to the leaf.

  • If the leaf only contains one item, insert our key into that leaf, since a leaf can contain 2 data items

  • If the leaf contains two items, this is an overflow. We use a split operation to fix this problem.

Overflow

A problem that occurs when we use ADD() in a (2,3) tree, but the leaf we ended up with already contains 2 items and it is full.

Split Algorithm

An approach to fix overflow.

1. Add the new key into that node with 2 keys.

2. Boot the middle key up to the parent node.

3. Split the remaining 2 keys into 2 leaves: one with the smaller key, and one with the larger key

4. If the node being split was the root, the tree now has a new root with the middle value as its key

In split operation, what should we do if the parent node also contains 2 keys already?

Continue to boot the middle value of the 3 keys up one level.

If the parent node happens to be a root node, make the tree higher by adding a new root at a new level, where the key of this new root node will also be the middle value.

Algorithm for ADD(D, Key, Element) in (2,3) Trees

• Searches for a node storing Key.

• For successful search, replaces the element in the node with Element.

• For unsuccessful search, adds the data item (Key, Element) to the leaf that was found.

• If overflow occurs, splits the leaf.

• If splitting leads to overflow in the parent, then the parent may need to be split as well.

• Splitting can propagate up to the root.

Algorithm for DELETE(D, Key)

• Searches for the node storing Key.

• If the node is an internal node, swaps the data item into a leaf.

• Deletes the data item.

• If underflow occurs, rearrange data items or fuse nodes.

• If fusing leads to underflow in the parent, then the parent and its sibling may need to be fused as well.

  • Fusing can propagate up to the root.

Worst-case cost of ADD(D, Key, Element)

• Search in θ(log n)

• Update in θ(1)

• Execute one split in θ(1)

• Number of splits is in θ(log n)

Worst-case total cost: θ(log n)

Worst-case cost of DELETE(D, Key)

• Search in θ(log n) (including finding of inorder successor)

• Update in θ(1)

• Execute one fuse in θ(1)

• Number of fuses is in θ(log n)

Worst-case total cost: θ(log n)