3.3.1.1. Binary Search Trees¶

A

B

A

B

3.3.1.2. BST as a Dictionary (1)¶

3.3.1.3. BST as a Dictionary (2)¶

3.3.1.4. BST findhelp¶

0 / 0 Settings

<<<>>>

• 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

Saving...
Server Error
Resubmit

3.3.1.5. BST inserthelp¶

0 / 0 Settings

<<<>>>

• 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

Saving...
Server Error
Resubmit

3.3.1.6. BST deletemax¶

0 / 0 Settings

<<<>>>

• // 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

Saving...
Server Error
Resubmit

3.3.1.7. BST removehelp¶

0 / 0 Settings

<<<>>>

• 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

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?