PowerPoint Presentation
Lecture 4 Pseudocode
Hashing
Chained Hash Tables
Open Addressing
Chained Hash Tables
How to implement dictionary operations with chaining
Search:
CHAINED-HASH-SEARCH(T, k)
search for an element with key k in list T [h(k)]
Running time: proportional to the length of the list of elements in slot h(k).
Insertion:
CHAINED-HASH-INSERT(T, x)
insert x at the head of list T[h(key[x])]
Worst-case running time is O(1).
Assumes that the element being inserted is not already in the list.
Takes an additional search to check if it was already inserted.
Deletion:
CHAINED-HASH-DELETE(T, x)
delete x from the list T [h(key[x])]
Given pointer x to the element to delete, so no search is needed to find this element.
Worst-case running time is O(1) time if the lists are doubly linked.
If the lists are singly linked, then deletion takes as long as searching: must find x predecessor in its list in order to correctly update next pointers.
Open addressing
Pseudocode for searching:
HASH-SEARCH(T, k)
i = 0
repeat
j = h(k, i)
if T [j ] == k
return j
else i = i + 1
until T[j] == NIL or i == m
return NIL
HASH-SEARCH returns the index of a slot containing key k, or NIL if the search is unsuccessful.
Pseudocode for insertion:
HASH-INSERT(T, k)
i = 0
repeat
j = h(k, i)
if T [j ] == NIL
T [j ] = k
return j
else i = i + 1
until i == m
error “hash table overflow”
HASH-INSERT returns the index of the slot that gets key k, or flags a hash table overflow error if if there is no empty slot in which to put key k.
Pseudocode for deletion:
HASH-DELETE(T, k)
i = 0
repeat
j = h(k, i)
if T [j ] == k
T [j ] = DELETED
return j
else i = i + 1
until T [j ] == NIL or i == m
error “element does not exist”
By implementing HASH-DELETE this way, HASH-INSERT must be modified to treat DELETED slots as empty ones.
Pseudocode for modified-insertion:
HASH-INSERT(T, k)
i = 0
repeat
j = h(k, i)
if T [j ] == NIL or T [j ] == DELETED
T [j ] = k
return j
else i = i + 1
until i == m
error “hash table overflow”
Binary Search Trees
Binary search tree: print keys in order
INORDER-TREE-WALK(x)
if x != NIL
then INORDER-TREE-WALK(left[x])
print key[x]
INORDER-TREE-WALK(right[x])
Querying a binary search tree
Pseudocode for searching:
TREE-SEARCH(x, k)
if x = NIL or k = key[x]
then return x
if k < key [x]
then return TREE-SEARCH(left[x], k)
else return TREE-SEARCH(right[x],k)
Initial call is TREE-SEARCH(root[T ], k).
Pseudocode for minimum and maximum:
TREE-MINIMUM(x)
while left[x] != NIL
x = left[x]
return x
TREE-MAXIMUM(x)
while right[x] != NIL
x = right[x]
return x
Pseudocode for successor:
TREE-SUCCESSOR(x)
if right[x] != NIL
then return TREE-MINIMUM(right[x])
y = p[x]
while y != NIL and x = right[y]
x = y
y = p[y]
return y
Insertion and Deletion
Pseudocode for insertion:
TREE-INSERT(T, k)
1. y = NIL
2. x = root[T]
3. while x != NIL
4. y = x
5. if key[z] < key[x]
6. then x = left[x]
7. else x = right[x]
8. p[z] = y
9. if y = NIL
10. then root[T] = z
11. else if key[z] < key[y]
12. then left[y] = z
13. else right[y] = z
Pseudocode for deletion:
TREE-DELETE(T, z)
1. if left[z] == NIL or right[z] == NIL
2. y = z // at most one child
3. else y = TREE-SUCCESSOR(z) // y has =< 1 child
4. if left[y] != NIL
5. x = left[y]
6. else x = right[y] // x is y’s child
7. if x != NIL // set up parent of x
8. p[x] = p[y]
9. if p[y] == NIL // deleting the only node
10. root[T] = x
11. else // set up the correct child
TREE-DELETE(T, z) -- continued
11. else // set up the correct child
12. if y == left[p[y]]
13. left[p[y]] = x
14. else right[p[y]] = x
15. if y != z // when z has two children
16. // copy y’s data into z
17. key[z] = key[y]
18. return y
/docProps/thumbnail.jpeg