CSC $220$ Data Structures

Homework #$4$

$($follows: L$8\mathrm{.}1$ Binary Search Trees & L$8\mathrm{.}22-3$ Trees$)$

Name: $\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_$ Due: Wed, Jan $24$th

$1.(2$pts$)$ Carry out the following operations showing the resulting binary search tree after all operations. Draw the tree in the space to the right of the operations. Assume the tree is initially empty $($i$.$e$.$ the root is null$).$

a$.$ insert$(45)$

b$.$ insert$(20)$

c$.$ insert$(30)$

d$.$ insert$(60)$

e$.$ insert$(80)$

f$.$ insert$(70)$

g$.$ insert$(10)$

$2.(3$pts$)$ Take the same tree from question $1,$ and show the result of running the following traversal operations. Assume each operation returns the integer values separated by commas as it processes each node.

a$.$ inorder$()$

b$.$ preorder$()$

c$.$ postorder$()$

$3.(4$pts$)$ Take the same tree from question $1,$ and show the resulting binary search tree after each of the following operations. After performing the operation, use the resulting tree for the next operation.

a$.$ delete$(30)$

b$.$ delete$(80)$

c$.$ delete$(45)$

d$.$ delete$(60)$

$4.(6$pts$)$ Carry out the following operations showing the resulting $2-3$ tree after each operation. Assume the tree is initially empty $($i$.$e$.$ the root is null$).$ After performing the operation, use the resulting tree for the next operation.

a$.$ insert$(45)$

b$.$ insert$(20)$

c$.$ insert$(30)$

d$.$ insert$(60)$

e$.$ insert$(80)$

f$.$ insert$(70)$

$*($OPTIONAL$)$ For further practice, figure out what the tree would look like if we inserted $65$ into the tree from part $($f$).$ What if we inserted $75$ into the tree from part $($f$).$ How about $85?$ Take the tree from part $($f$)$ as the starting point each time. This will help you with cascading splits which may be useful for the exam. For further practice, do the problems from the workbook.