AVL Trees - Java Data Structures & Algorithms

Question

Can someone help with this AVL tree deletion?

Delete 7,5,9 from the following AVL tree?

AVL tree represented as an array(note that null denotes nodes with no values)

9, 5, 12, 3, 6, 11, 14, 2, 4, null, 7, 10, null, 13, 15

I would appreciate if I can have a step-by-step guidance. Many thanks!

Answer 1

Pulls all of them out of the tree and puts them into the array, and deletes 5,7,9

{2,3,4,6,10,11,12,13,14,15}

step 1) find the MEDIAN, the middle one : 11

that is the top root of the next level

step 2) then split the array into 2 pieces, {2,3,4,6}, {12,13,14,15}

recursively repeat the steps of each array slice

lower sub-array:

median is 4 : children are 3 and 6

2 is child of 3 <--- 3 layers deep

higher sub-array:

median is 13

children are 12 and 14;

15 is child of 14 <--- 3 layers deep

the tree is balanced.

Note that in PRACTICE, since you are using the array anyway, it is faster and

more efficient with respect to time and space, to sort the array using Quicksort

algorithm, which works very similar to the algorithm of the binary tree...

the left and right branches of the tree are done via the recursive quick sort calls:

1) selects a PIVOT ELEMENT from the array ... typically the MEDIAN of the data

2) rearranges the array so that all of the elements to the LEFT of the pivot are LESS than the pivot;

rearranges the array so that all of the elements to the RIGHT of the pivot are GREATER than the pivot

Recursively sorts the two sub-arrays in this way using the same quicksort algorithm.

the stopping case is when the left and right array indices differ by one or zero, in which case

the array of size one or zero is sorted by default automatically.

I have uploaded a picture for you: balanced binary tree, and it is a jpeg picture.