6.14.1.1. Binary Search Trees¶

A

B

A

B

(a)

(b)

A

B

EMPTY

A

EMPTY

B

(c)

(d)

6.14.1.2. BST as a Dictionary (1)¶

6.14.1.3. BST as a Dictionary (2)¶

6.14.1.4. BST findhelp¶

1 / 17 Settings

<<<>>>

Consider searching for the record with key value 32 in this tree. We call the findhelp method with a pointer to the BST root (the node with key value 37).

37

24

42

7

32

2

42

120

40

rt

Saving...
Server Error
Resubmit

6.14.1.5. BST inserthelp¶

1 / 22 Settings

<<<>>>

Consider inserting a record with key value 30 in this tree. We call the inserthelp method with a pointer to the BST root (the node with value 37).

37

24

42

7

32

2

42

120

40

30

rt

root

Saving...
Server Error
Resubmit

6.14.1.6. BST deletemax¶

1 / 6 Settings

<<<>>>

To remove the node with the maximum key value from a subtree, first find that node by starting at the subtree root and continuously move down the right link until there is no further right link to follow.

10

5

20

12

15

rt

Saving...
Server Error
Resubmit

6.14.1.7. BST removehelp¶

1 / 46 Settings

<<<>>>

Let's look a few examples for removehelp. We will start with an easy case. Let's see what happens when we delete 30 from this tree.

37

24

42

7

32

2

30

42

120

40

30

30

rt

temp

Saving...
Server Error
Resubmit

6.14.1.8. .¶

.

6.14.1.9. BST Analysis¶

Find: $O(d)$

Insert: $O(d)$

Delete: $O(d)$

$d =$ depth of the tree

$d$ is $O(\log n)$ if the tree is balanced.

What is the worst case cost? When?