3.3.1.1. Binary Search Trees¶

A

B

A

B

(a)

(b)

A

B

EMPTY

A

EMPTY

B

(c)

(d)

3.3.1.2. BST as a Dictionary (1)¶

3.3.1.3. BST as a Dictionary (2)¶

3.3.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).

• private E findhelp(BSTNode<E> rt, E key) {
• if (rt == null) { return null; }
• if (rt.value().compareTo(key) > 0) {
• return findhelp(rt.left(), key);
• }
• else if (rt.value().compareTo(key) == 0) {
• return rt.value();
• }
• else { return findhelp(rt.right(), key); }
• }

37

24

42

7

32

2

42

120

40

rt

Saving...
Server Error
Resubmit

3.3.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).

• private BSTNode<E> inserthelp(BSTNode<E> rt, E e) {
• if (rt == null) { return new BSTNode<E>(e); }
• if (rt.value().compareTo(e) >= 0) {
• rt.setLeft(inserthelp(rt.left(), e));
• }
• else{
• rt.setRight(inserthelp(rt.right(), e));
• }
• return rt;
• }

37

24

42

7

32

2

42

120

40

30

rt

root

Saving...
Server Error
Resubmit

3.3.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.

• // Delete the maximum valued element in a subtree
• private BSTNode<E> deletemax(BSTNode<E> rt) {
• if (rt.right() == null) { return rt.left(); }
• rt.setRight(deletemax(rt.right()));
• return rt;
• }

10

5

20

12

15

rt

Saving...
Server Error
Resubmit

3.3.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.

• private BSTNode<E> removehelp(BSTNode<E> rt, E key) {
• if (rt == null) { return null; }
• if (rt.value().compareTo(key) > 0) {
• rt.setLeft(removehelp(rt.left(), key));
• }
• else if (rt.value().compareTo(key) < 0) {
• rt.setRight(removehelp(rt.right(), key));
• }
• else { // Found it
• if (rt.left() == null) { return rt.right(); }
• else if (rt.right() == null) { return rt.left(); }
• else { // Two children
• BSTNode<E> temp = getmax(rt.left());
• rt.setValue(temp.value());
• rt.setLeft(deletemax(rt.left()));
• }
• }
• return rt;
• }

37

24

42

7

32

2

30

42

120

40

30

30

rt

temp

Saving...
Server Error
Resubmit

3.3.1.8. .¶

.

3.3.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?