1 of 69

Lecture 9: Binary Search Trees

CSE 373: Data Structures and Algorithms

1

2 of 69

Announcements

Exercise 2 – Due Friday July 15th
Project 2 is Due Wednesday July 20th
- Once again please start now, if you wait you’ll be less likely to meet with the TA’s!

No poll today, finish Monday’s poll (extended to Friday at 1:00PM due to broken tinyurl link)

https://forms.gle/ZPiu8AZmCGaCdjzd7

CSE 373 22 SP – CHAMPION

2

3 of 69

Strategies to handle hash collision

There are multiple strategies. In this class, we’ll cover the following ones:

1. Separate chaining
2. Open addressing

Linear probing
Quadratic probing
Double hashing

CSE 373 AU 18 – SHRI MARE

3

4 of 69

Separate chaining

// some pseudocode

public boolean containsKey(int key) {

int bucketIndex = key % data.length;

loop through data[bucketIndex]

return true if we find the key in

data[bucketIndex]

return false if we get to here (didn’t

find it)

}

CSE 373 ROBBIE WEBER + HANNAH TANG

4

Reminder: the implementations of put/get/containsKey are all very similar, and almost always will have the same complexity class runtime

runtime analysis

Are there different possible states for our Hash Map that make this code run slower/faster, assuming there are already n key-value pairs being stored?

Yes! If we had to do a lot of loop iterations to find the key in the bucket, our code will run slower.

5 of 69

Handling Collisions

Solution 2: Open Addressing
Resolves collisions by choosing a different location to store a value if natural choice is already full.
Type 1: Linear Probing
If there is a collision, keep checking the next element until we find an open spot.
int findFinalLocation(Key s)
int naturalHash = this.getHash(s);

int index = natrualHash % TableSize;

while (index in use) {

i++;

index = (naturalHash + i) % TableSize;

}

return index;

CSE 373 SP 18 - KASEY CHAMPION

5

6 of 69

Linear Probing

CSE 373 SP 18 - KASEY CHAMPION

6

0	1	2	3	4	5	6	7	8	9

Insert the following values into the Hash Table using a hashFunction of % table size and linear probing to resolve collisions

1, 5, 11, 7, 12, 17, 6, 25

1

5

11

7

12

17

6

25

7 of 69

Linear Probing

CSE 373 SP 18 - KASEY CHAMPION

7

0	1	2	3	4	5	6	7	8	9

Insert the following values into the Hash Table using a hashFunction of % table size and linear probing to resolve collisions

38, 19, 8, 109, 10

38

19

8

109

10

Problem:

Linear probing causes clustering
Clustering causes more looping when probing

Primary Clustering

When probing causes long chains of occupied slots within a hash table

8 of 69

Runtime

When is runtime good?
When we hit an empty slot

(or an empty slot is a very short distance away)

When is runtime bad?
When we hit a “cluster”

Maximum Load Factor?
λ at most 1.0

When do we resize the array?
λ ≈ ½ is a good rule of thumb

CSE 373 SP 18 - KASEY CHAMPION

8

9 of 69

Can we do better?

CSE 373 SP 18 - KASEY CHAMPION

9

10 of 69

Quadratic Probing

CSE 373 SP 18 - KASEY CHAMPION

10

0	1	2	3	4	5	6	7	8	9

(49 % 10 + 0 * 0) % 10 = 9

(49 % 10 + 1 * 1) % 10 = 0

(58 % 10 + 0 * 0) % 10 = 8

(58 % 10 + 1 * 1) % 10 = 9

(58 % 10 + 2 * 2) % 10 = 2

89

18

49

Insert the following values into the Hash Table using a hashFunction of % table size and quadratic probing to resolve collisions

89, 18, 49, 58, 79, 27

58

79

(79 % 10 + 0 * 0) % 10 = 9

(79 % 10 + 1 * 1) % 10 = 0

(79 % 10 + 2 * 2) % 10 = 3

Problems:

If λ≥ ½ we might never find an empty spot

Infinite loop!

Can still get clusters

27

Now try to insert 9.

Uh-oh

11 of 69

Quadratic Probing

There were empty spots. What Gives?

Quadratic probing is not guaranteed to check every possible spot in the hash table

The following is true:

Notice we have to assume p is prime to get that guarantee

12 of 69

Secondary Clustering

CSE 373 SP 18 - KASEY CHAMPION

12

0	1	2	3	4	5	6	7	8	9

Insert the following values into the Hash Table using a hashFunction of % table size and quadratic probing to resolve collisions

19, 39, 29, 9

39

29

19

9

Secondary Clustering

When using quadratic probing sometimes need to probe the same sequence of table cells, not necessarily next to one another

13 of 69

Probing

h(k) = the natural hash
h’(k, i) = resulting hash after probing
i = iteration of the probe
T = table size

Linear Probing:
h’(k, i) = (h(k) + i) % T
Quadratic Probing
h’(k, i) = (h(k) + i²) % T

CSE 373 SP 18 - KASEY CHAMPION

13

14 of 69

Questions

Topics Covered:

Writing good hash functions
Open addressing to resolve collisions:

Linear probing
Quadratic probing

CSE 373 20 SP – CHAMPION & CHUN

14

15 of 69

Double Hashing

Probing causes us to check the same indices over and over- can we check different ones instead?

Use a second hash function!
h’(k, i) = (h(k) + i * g(k)) % T

int findFinalLocation(Key s)
int naturalHash = this.getHash(s);

int index = natrualHash % TableSize;

while (index in use) {

i++;

index = (naturalHash + i*jumpHash(s)) % TableSize;

}

return index;

CSE 373 SP 18 - KASEY CHAMPION

15

<- Most effective if g(k) returns value relatively prime to table size

16 of 69

Second Hash Function

Effective if g(k) returns a value that is relatively prime to table size

If T is a power of 2, make g(k) return an odd integer
If T is a prime, make g(k) return anything except a multiple of the TableSize

CSE 373 SP 18 - KASEY CHAMPION

16

17 of 69

Resizing: Open Addressing

18 of 69

Running Times

CSE 332 SU 18 – ROBBIE WEBER

19 of 69

In-Practice

20 of 69

Summary

1. Pick a hash function to:

Avoid collisions
Uniformly distribute data
Reduce hash computational costs

2. Pick a collision strategy

Chaining

LinkedList
AVL Tree

Probing

Linear
Quadratic
Double Hashing

CSE 373 SP 18 - KASEY CHAMPION

20

No clustering

Potentially more “compact” (λ can be higher)

Managing clustering can be tricky

Less compact (keep λ < ½)

Array lookups tend to be a constant factor faster than traversing pointers

21 of 69

Summary

22 of 69

Extra optimizations

CSE 373 SP 18 - KASEY CHAMPION

22

23 of 69

Other Hashing Applications

We use it for hash tables but there are lots of uses! Hashing is a really good way of taking arbitrary data and creating a succinct and unique summary of data.

CSE 373 20 WI – HANNAH TANG

23

Cryptography

Hashing also ”hides” the data by translating it, this can be used for security

For password verification: Storing passwords in plaintext is insecure. So your passwords are stored as a hash
Digital signatures

Fingerprinting

git hashes (“identification”)

That crazy number that is attached to each of your commits
SHA-1 hash incorporates the contents of your change, the name of the files and the lines of the files you changes

Ad Tracking

track who has seen an ad if they saw it on a different device (if they saw it on their phone don’t want to show it on their laptop)
https://panopticlick.eff.org will show you what is being hashed about you

YouTube Content ID

Do two files contain the same thing? Copyright infringement
Change the files a bit!

Caching

you’ve downloaded a large video file, You want to know if a new version is available, Rather than re-downloading the entire file, compare your file’s hash value with the server's hash value.

File Verification / Error Checking:

compare the hash of a file instead of the file itself
Find similar substrings in a large collection of strings – detecting plagiarism

24 of 69

Binary Search Trees

CSE 373 22 SP – CHAMPION

24

25 of 69

Binary Trees

A tree is a collection of nodes

Each node has at most 1 parent and anywhere from 0 to 2 children
pretty similar to node based structures we’ve seen before (linked-lists)

public class Node<K> {

K data;

Node<K> left;

Node<K> right;

}

Root node: the single node with no parent, “top” of the tree. Often called the ‘overallRoot’
Leaf node: a node with no children
Subtree: a node and all it descendants
Height: the number of edges contained in the longest path from root node to some leaf node

CSE 373 SP 18 - KASEY CHAMPION

25

1

2

5

3

6

7

4

8

26 of 69

Tree Height

What is the height (the number of edges contained in the longest path from root node to some leaf node ) of the following binary trees?

CSE 373 SP 18 - KASEY CHAMPION

26

1

2

5

7

overallRoot

null

Height = 2

Height = 0

Height = -1 or NA

27 of 69

Other Useful Binary Tree Numbers

h=3

For a binary tree of height h:

28 of 69

Binary Search Tree (BST)

CSE 373 SP 18 - KASEY CHAMPION

28

10

8

32

2

11

50

5

38

9

29 of 69

BST Ordering Applies Recursively

9

3

10

1

5

30

9

3

10

1

5

30

< 9

> 9

9

3

10

1

5

30

< 9

> 9

< 3 & < 9

> 3 & < 9

30 of 69

Aside Anything Can Be a Map

Want to make a tree implement the Map ADT?

No problem – just add a value field to the nodes, so each node represents a key/value pair.

public class Node<K, V> {

K key;

V value;

Node<K, V> left;

Node<K, V> right;

}

For simplicity, we’ll just talk about the keys

Interactions between nodes are based off of keys (e.g. BST sorts by keys)
In other words, keys determine where the nodes go

1

aqua

31 of 69

a note about keys/maps

In reality, just like with HashMap all the elements need to store both the key and the value as a pair. So the node class would just have an extra field to store both the key and the value instead of just one piece of data.

public class Node<K, V> {

K key;

V value;

Node<K, V> left;

Node<K, V> right;

}

For simplicity we’re just going to show the keys, since that’s what will determine the sorted-ness and how the elements will interact with each other. This is just like in hash map where the keys determine where the elements go (we hash the keys and not the values).

32 of 69

Binary Trees vs Binary Search Trees:�containsKey(2)

32

11

9

50

8

2

5

10

38

10

8

32

2

11

50

5

38

9

33 of 69

Binary Tree vs. BST: containsKey(5)

10

9

1

3

2

30

14

5

9

3

10

1

5

30

2

14

Without BST Invariant

With BST Invariant

Nodes that

are searched

34 of 69

Binary Trees vs Binary Search Trees: containsKey(2)

public boolean containsKeyBT(node, key) {
if (node == null) {
return false;
} else if (node.key == key) {
return true;
} else {
return containsKeyBT(node.left) ||
containsKeyBT(node.right);
}
}

public boolean containsKeyBST(node, key) {

if (node == null) {

return false;
} else if (node.key == key) {
return true;
} else {
if (key <= node.key) {
return containsKeyBST(node.left);
} else {
return containsKeyBST(node.right);
}
}
}

9

2

1

3

6

5

7

4

8

10

12

14

11

15

13

35 of 69

BST containsKey runtime

public boolean containsKeyBST(node, key) {

if (node == null) {

return false;
} else if (node.key == key) {
return true;
} else {
if (key <= node.key) {
return containsKeyBST(node.left);
} else {
return containsKeyBST(node.right);
}
}
}

9

2

1

3

6

5

7

4

8

10

12

14

11

15

13

For the tree on the right, what are some possible interesting cases (best/worst/other?) that could come up? Consider what values of key could affect the runtime

best: 8, runtime will be O(1) since it will end immediately
worst: -1 since it has to traverse all the way down (other values will work for this)

36 of 69

Is it possible to do worse than O(log n) 😈

We only considered changing the key parameter for that one particular BST in our last thought exercise, but what about if we consider the different possible arrangements of the BST as well?
Let’s try to come up with a valid BST with the numbers 1 through 15 (same as previous tree) and key combination that result in a worse runtime for containsKey.

1

2

3

4

…

15

containsKey(16)

37 of 69

BST different states

Two different extreme states our BST could be in (there’s in-between, but it’s easiest to focus on the extremes as a starting point). Try containsKey(15) to see what the difference is.

Perfectly balanced – for every node, its descendants are split evenly between left and right subtrees.

Degenerate – for every node, all of its descendants are in the right subtree.

9

2

1

3

6

5

7

4

8

10

12

15

14

11

13

1

2

3

4

15

…

38 of 69

Questions break -- Anything y’all want to review / restate?

So far:

Binary Trees, definitions
Binary Search Tree, invariants
Best/Worst case runtimes for BTs and BSTs

where the key is located
how the tree is structured

39 of 69

How are we going to make this simpler / more efficient? Let’s enforce some invariants!

Observation: What was important was actually the height of the tree.

Height: number of edges on the longest path from the root to a leaf.

That’s the number of recursive calls we’re going to make

And each recursive call does a constant number of operations.

The BST invariant makes it easy to know where to find a key
But it doesn’t force the tree to be short.

Let’s add an invariant that forces the height to be short!

40 of 69

Invariants

41 of 69

Avoiding 𝚹(n) Behavior

Here are some invariants you might try. �Can you maintain them? If not what can go wrong?
Do you think they are strong enough to make containsKey efficient?
Try to come up with BSTs that show these rules aren’t useful / too strict.

Root Balanced: The root must have the same number of nodes in its left and right subtrees

Recursively Balanced: Every node must have the same number of nodes in its left and right subtrees.

Root Height Balanced: The left and right subtrees of the root must have the same height.

42 of 69

Take 1 minute to consider this question and then we’ll move to breakouts to discuss! (See chat for tips on moving discussion along + general reminders. Note that you’ll be prepping now so you have stuff to say / questions to ask each other. We’re still experimenting w/ breakouts / trying more strategies with them to make them successful, thanks for your patience.)

Here are some invariants you might try. �Can you maintain them? If not what can go wrong?
Do you think they are strong enough to make containsKey efficient?
Try to come up with BSTs that show these rules aren’t useful / too strict.

Root Balanced: The root must have the same number of nodes in its left and right subtrees

Recursively Balanced: Every node must have the same number of nodes in its left and right subtrees.

Root Height Balanced: The left and right subtrees of the root must have the same height.

43 of 69

too weak

Root Balanced: The root must have the same number of nodes in its left and right subtrees

44 of 69

too strong

Recursively Balanced: Every node must have the same number of nodes in its left and right subtrees.

45 of 69

too weak

Root Height Balanced: The left and right subtrees of the root must have the same height.

46 of 69

Invariant Lessons

Need requirements everywhere, not just at root
Forcing things to be exactly equal is too difficult to maintain.

47 of 69

Roadmap

Binary Trees
Binary Search Trees, invariants

runtimes

AVL Trees, invariants

48 of 69

Avoiding the Degenerate Tree

AVL invariant: For every node, the height of its left subtree and right subtree differ by at most 1.

An AVL tree is a binary search tree that also meets the following invariant

49 of 69

Practice w AVL invariants

AVL invariant: For every node, the height of its left subtree and right subtree differ by at most 1.

Is this a valid AVL tree?

4

5

2

7

3

9

8

10

6

50 of 69

Are These AVL Trees?

6

4

2

7

3

9

8

10

5

4

5

2

7

3

9

8

10

6

51 of 69

Insertion

What happens if when we do an insertion, we break the AVL condition?

1

2

3

1

2

3

52 of 69

Left Rotation

x

y

z

Rest of the tree

UNBALANCED

Right subtree is 2 longer

A

B

C

D

x

y

z

Rest of the tree

A

B

C

D

BALANCED

Right subtree is 1 longer

53 of 69

6

8

1

3

10

9

7

2

4

5

11

54 of 69

6

8

1

3

10

9

7

2

4

5

11

55 of 69

9

7

4

8

6

5

1

3

2

10

11

56 of 69

Meme break (it’s from some marvel movie that I haven’t watched -- you’re not alone if you don’t get this reference)

57 of 69

Right rotation

1

2

3

1

2

3

Just like a left roation, just reflected.

58 of 69

It Gets More Complicated

1

3

2

Can’t do a left rotation

Do a “right” rotation around 3 first.

1

3

2

Now do a left rotation.

1

2

3

There’s a “kink” in the tree where the insertion happened.

59 of 69

Right Left Rotation

x

z

y

Rest of the tree

A

B

C

D

x

y

z

Rest of the tree

A

B

C

D

BALANCED

Right subtree is 1 longer

UNBALANCED

Right subtree is 2 longer

Left subtree is

1 longer

60 of 69

AVL Example: 8,9,10,12,11

CSE 373 SU 18 – BEN JONES

60

8

9

10

61 of 69

AVL Example: 8,9,10,12,11

CSE 373 SU 18 – BEN JONES

61

8

9

10

62 of 69

AVL Example: 8,9,10,12,11

CSE 373 SU 18 – BEN JONES

62

8

11

9

10

12

63 of 69

AVL Example: 8,9,10,12,11

CSE 373 SU 18 – BEN JONES

63

8

11

9

10

12

64 of 69

AVL Example: 8,9,10,12,11

CSE 373 SU 18 – BEN JONES

64

8

9

10

11

12

65 of 69

How Long Does Rebalancing Take?

Assume we store in each node the height of its subtree.
How do we find an unbalanced node?

How many rotations might we have to do?

66 of 69

How Long Does Rebalancing Take?

Assume we store in each node the height of its subtree.
How do we find an unbalanced node?

Just go back up the tree from where we inserted.

How many rotations might we have to do?

Just a single or double rotation on the lowest unbalanced node.
A rotation will cause the subtree rooted where the rotation happens to have the same height it had before insertion

log(n) time to traverse to a leaf of the tree
log(n) time to find the imbalanced node
constant time to do the rotation(s)
Theta(log(n)) time for put (the worst case for all interesting + common AVL methods (get/containsKey/put is logarithmic time)

67 of 69

6

8

1

3

10

9

7

2

4

5

11

68 of 69

9

7

4

8

6

5

1

3

2

10

11

69 of 69

Deletion