08-Dictionary binary Search Trees PDF

Preview

Summary

Assignment...

Description

CSI2110 Data Structures and Algorithms 1

The Dictionary ADT The dictionary ADT models a searchable collection of key-element items The main operations of a dictionary are searching, inserting, and deleting items Multiple items with the same key are allowed Applications: n

address book

n

credit card authorization

mapping host names (e.g., cs16.net) to internet addresses (e.g., 128.148.34.101) n

n

English dictionary 2

Dictionary ADT methods: findElement(k): if the dictionary has an item with key k, returns its element, else, returns the special element NO_SUCH_KEY

insertItem(k, o): inserts item (k, o) into the dictionary removeElement(k): if the dictionary has an item with key k, removes it from the dictionary and returns its element, else returns the special element NO_SUCH_KEY

size(), isEmpty() keys(), Elements() findAllElements(k), removeAllElements(k)

3

Implementing a Dictionary with an Unordered Sequence

• searching and removing takes O(n) time • inserting takes O(1) time • applications to log files (frequent insertions, rare searches and removals)

4

Implementing a Dictionary with an Ordered Sequence

• searching takes O(log n) time (binary search) • inserting and removing takes O(n) time • application to look-up tables (frequent searches, rare insertions and removals)

5

Binary Search • narrow down the search range in stages • “high-low” game • Example: findElement(7)

0

1

3

4

5

7

1

0

3

4

5

m

l 0

9

11

14

16

18

19

m

l 0

8

1 1

3 3

7

h

8

9

11

14

16

18

19

8

9

11

14

16

18

19

8

9

11

14

16

18

19

h 4

5

7

l

m

h

4

5

7

l=m =h

6

Pseudocode for Binary Search Algorithm BinarySearch(S, k, low, high) if low > high then return NO_SUCH_KEY else mid ¬ (low+high) / 2 if k = key(mid) then return key(mid) else if k < key(mid) then return BinarySearch(S, k, low, mid-1) else return BinarySearch(S, k, mid+1, high) 2

4

5

7

8

9

12

low 2

14

17

19

22

27

28

33

4

5

7

8

9

12

14

4

5

7

8

9

12

14

37 high

mid 17

19

22

low 2

25

17

25

27

28

33

high

mid

19 22

low mid

25

37

27

28

33

37

7

Running Time of Binary Search • The range of candidate items to be searched is halved after each comparison

In the array-based implementation, access by rank takes O(1) 8 time, thus binary search runs in O(log n) time

Running Time of Binary Search • binary search runs in O(log n) time for findElement(k) • If we need to find all elements with a given key (findAllElements(k)), it runs in O(log n + s), where s is the number of element of elements in the iterator returned. – Simply do a binary search to find an element equal to k. Then step back through the array until you reach the first element equal to k. Finally, step forward through the area adding each element to the iterator until you reach the first element that is not equal to k. This takes O(logn) time for the search and then at most s time to search back to the beginning of the run of k’s and s time return all of the elements k. Therefore we have a solution running in at most O(log n + s) time.

9

New Insertion Sort What is the running time of the insertion sort, using a sequence implemented with an array?

If we use a binary search to do the insertions?

10

Binary Search Tree Searching Cost of Searching Insertion Deletion

< 2 1

6 9

> 4 =

8

11

Binary Search Trees • A binary search tree is a binary tree T such that – each internal node stores an item (k, e) of a dictionary. – keys stored at nodes in the left subtree of v are less than or equal to k. – keys stored at nodes in the right subtree of v are greater than or equal to k. – external nodes do not hold elements but serve as place holders.

12

Gregor

Fabio

Bob

Nicole

Frank

13

10 3 1

17 8

5

15

20

9

Question: How can we traverse the tree so that we visit the elements in increasing key order?

14

Operations

Searching: findElement(k): Inserting: insertItem(k, o): Removing: removeElement(k):

15

Search Algorithm findElement(k, v) • To search for a key k, if T.isExternal (v) we trace a downward path starting at the root return NO_SUCH_KEY if k < key(v) • The next node visited depends on the return findElement(k, T.leftChild(v)) outcome of the else if k = key(v) comparison of k with the return element(v) key of the current node else { k > key(v) } • If we reach a leaf, the return findElement(k, T.rightChild(v)) key is not found and we return NO_SUCH_KEY 6 < • Example: 2 9 findElement(4) > 1

4 =

8

16

Search Example I Successful findElement(76) 76>44 7665 76 key(v)} return findAllElements(k,T,rightChild(v)) Note that after finding k, if it occurs again, it will be in the left most internal 18 node of the right subtree.

Search Example II Unsuccessful findElement(25) 2517 25...