Trees

CSE 332 (Section 4)

10/20/2022

Original slides by: Louis Maliyam • Monty Nitschke • Kevin Pham

Announcements

• Project 2 is out, please START EARLY!
• The P1 Hidden Test rerunner is available for you to fix any bugs from P1
• P2 is much harder than P1, especially on Checkpoint 2!
• P2 Checkpoint 1 due Thursday (10/20 11:59 PM)
• EX07 due 10/24
• We’re skipping EX05 and EX06 this quarter

​

AVL Tree

AVL Tree Warm-up Questions!

Are the following statements True or False?

​

• Any AVL tree is a BST (binary search tree). True / False
• Any BST is an AVL tree. True / False
• AVL tree is preferred over BST because AVL tree can re-balance itself. True / False

An example of AVL tree from wikipedia

Problem 0

Let’s discuss!

(Q0) The ABC’s of AVL Trees

What are the constraints on the data types you can store in an AVL tree? When is an AVL tree preferred over another dictionary implementation, such as HashMap?

​

​

(Q0) The ABC’s of AVL Trees

What are the constraints on the data types you can store in an AVL tree? When is an AVL tree preferred over another dictionary implementation, such as HashMap?

​

​

• Data types must be Comparable to be stored in an AVL tree (think TreeMap)

​

• We prefer an AVL trees when we want to be able to iterate in sorted order

AVL Tree (Rotations)

Review from lecture

Case 1

Case 2

Case 3

Case 4

We will call them

Rotation Review (Single) - Case 1

• Imbalance at the red node due to insertion into the left subtree of left child

Note: Actual height and subtrees not shown

rotateWithLeft(6)

Rotation Review (Single) - Case 4

• Imbalance at the red node due to insertion into the right subtree of right child

Note: Actual height and subtrees not shown

rotateWithRight(6)

Rotation Review (Double) - Case 3

• Imbalance at the red node due to insertion into the left subtree of right child

• Still not fixed, will need to apply single rotation afterwards to a right-right tree

Note: Actual height and subtrees not shown

rotateWithLeft(9)

Point to new sub-root

Rotation Review (Double) - Case 3

• Imbalance at the red node due to insertion into the left subtree of right child, now become a right-right tree (Case 4)

Note: Actual height and subtrees not shown

rotateWithRight(5)

Rotation Review (Double) - Case 2

• Imbalance at the red node due to insertion into the right subtree of left child

• Still not fixed, will need to apply single rotation afterwards to a left-left tree

Note: Actual height and subtrees not shown

rotateWithRight(3)

Point to new sub-root

Rotation Review (Double) - Case 2

• Imbalance at the red node due to insertion into the right subtree of left child, now become a left-left tree (Case 1)

Note: Actual height and subtrees not shown

rotateWithLeft(6)

Problem 1

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(10)

No imbalance!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(4)

No imbalance!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(5)

Imbalance at 10

Case 2

rotateWithRight(4)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(5)

Imbalance at 10

Case 2

rotateWithLeft(10)

rotateWithRight(4)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(5)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(8)

No imbalance!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(9)

Imbalance at 10

Case 2

rotateWithRight(8)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(9)

Imbalance at 10

Case 2

rotateWithLeft(10)

rotateWithRight(8)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(9)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(6)

Imbalance at 5

Case 3

rotateWithLeft(9)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(6)

Imbalance at 5

Case 3

rotateWithRight(5)

rotateWithLeft(9)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(6)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(11)

Imbalance at 9

Case 4

rotateWithRight(9)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(11)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(3)

No imbalance!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(2)

Imbalance at 4

Case 1

rotateWithLeft(4)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(2)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(1)

Imbalance at 5

Case 1

rotateWithLeft(5)

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(1)

Balanced - YAY!

(Q1) Let’s Plant an AVL Tree

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

insert(14)

No imbalance!

(Q1) Let’s Plant an AVL Tree - Breakout 1

10

4

5

8

9

6

11

3

2

1

14

Insert these values in order into an initially empty AVL Tree

B-Trees

Review from lecture

M=3 and L=3

No. of children

(for internal nodes)

No. of key-value pairs (for leaf nodes)

Problem 4

(Q4) The ABC’s of B-Trees

What properties must a B-tree of n values have with given values for M and L?

(Q4) The ABC’s of B-Trees

What properties must a B-tree of n values have with given values for M and L?

• Order Property
• Every subtree between keys a and b contains all data x where
• The values in the leaves are in key sorted order
• The keys in the internal nodes are stored in sorted order
• Structure Property
• If
• The root is a leaf with n values
• Otherwise: Root is an internal node with between 2 and M children
• All internal nodes are half-full (ie have between and M children)
• All leaf nodes are half-full (ie have between and L key-value pairs)
• All leaf nodes must be at the same depth

Problem 7(a)

(Q7a) B-Trees

10

10

Node Bank

(copy and paste to form your own B Tree)

10

10

10

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

insert(12)

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

24

insert(24)

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

24

36

insert(36)

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

insert(17)

Structure issue

12

17

24

36

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

17

insert(17)

Structure issue

Split leaf node

24

36

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

17

insert(17)

Structure issue

Attach to new internal node

24

36

24

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

12

17

18

insert(18)

24

36

24

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(5)

24

36

24

18

Structure issue

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(5)

24

36

24

18

Structure issue

Split leaf node

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(5)

24

36

17

24

18

Structure issue

Attach to internal node & Update sign post

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(22)

24

36

17

24

18

22

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

Structure issue

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

Structure issue

Split leaf node

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

Try attaching to internal node

20

Structure issue

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

20

Another structure issue

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

Another structure issue

Split internal node

(Q7a) B-Trees

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

5

12

17

insert(20)

24

36

17

24

18

20

22

Another structure issue

Attach to new internal node

20

(Q7a) B-Trees - Breakout 1

10

10

Node Bank

(copy and paste to form your own B+ Tree)

10

10

10

Insert the following into an empty B-Tree with M=3 and L=3: 12, 24, 36, 17, 18, 5, 22, 20.

Problem 7(b)

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

5

12

17

24

36

17

24

18

20

22

20

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

5

12

18

24

36

18

24

20

22

20

delete(17)

Structure issue

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

5

12

24

36

18

24

18

20

22

20

delete(17)

Structure issue

Merge with neighboring leaf node

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

5

12

24

36

18

24

18

20

22

20

delete(17)

Structure issue

Another structure issue

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

5

12

24

36

18

24

18

20

22

delete(17)

Structure issue

Another structure issue

Delete root internal node

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(17)

Structure issue

Another structure issue

Merge internal nodes and update sign post.

5

12

20

24

36

20

24

22

18

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(12)

5

18

20

24

36

20

24

22

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(22)

5

18

20

24

36

20

24

Structure issue

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(22)

5

18

24

36

20

24

20

Structure issue

Merge with neighboring leaf node.

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(22)

Structure issue

Update sign post.

5

18

20

24

36

24

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(5)

18

20

24

36

24

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(36)

18

20

24

24

Structure issue

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(36)

18

20

24

Structure issue

Delete internal node.

(Q7b) B-Trees

Delete 17, 12, 22, 5, 36.

delete(36)

Structure issue

Merge leaf nodes.

18

20

24

Final Result!

(Q7b) B-Tree - Breakout 1

Delete 17, 12, 22, 5, 36.

5

12

17

24

36

17

24

18

20

22

20

Math of B-Trees

Fitting a B Tree node in a page!

Assume that

• 1 page (on disk) size is p bytes
• Key size is k bytes
• Pointer size is t bytes
• Key-value pair size is v bytes

​

How should we decide parameters M and L for our B tree to efficiently use the memory to the fullest?

Internal Nodes

Leaf Nodes