SOLUTION:
The answer is
m h + 1.
The proof is by induction on .
m (h-1) + 1 + (m-1) + 1 = m(h-1) + m + 1 = m h + 1
nodes.
Assuming it is an AVL tree, show the state of the tree after inserting 10 and then again after deleting 28.
SOLUTION:
SOLUTION:
x0
and less than x1
. What is the running time of your
algorithm? (More credit will be given for an efficient algorithm.)
You may assume the following declaration for tree nodes:
struct TreeNode { float x; TreeNode * left; TreeNode * right; }Start from the following prototype and assume the function is initially passed a pointer to the root:
int Count( TreeNode * T, float x0, float x1 )
Solution:
{ if ( T == NULL ) return 0; else if ( T->x <= x0 ) return Count( T->right, x0, x1); else if ( T->x >= x1 ) return Count( T->left, x0, x1); else return 1 + Count( T->left, x0, x1 ) + Count( T->right, x0, x1 ); }Showing that this is in fact
x0
and x1
two recursive calls are made. These are calls made at the else
statement, resulting in the k part of the else if
statements. These correspond to walking down the left and right
boundaries of the region of the tree containing the values between
x0
and x1
.
struct Avl_Node { float Element; Avl_Node *Left; Avl_Node *Right; int Height; };Your function should calculate the heights of the nodes and it should return a pointer to the root of the tree. You do not need to prove that the result is an AVL tree and you do not need to prove the function requires O(N) time. Here is a prototype
Avl_Node * ArrayToAVLTree( float values[], int N )
Solution:
Avl_Node * ArrayToAVLTree( float values[], int N ) { return ArrayToAVLTree( values, 0, N-1 ); } Avl_Node * ArrayToAVLTree( float values[], int low, int high ) { if ( low > high ) return NULL; int mid = (low+high)/2; Avl_Node * node = new Avl_Node; node->Element = values[mid]; node->Left = ArrayToAVLTree( values, low, mid-1 ); node->Right = ArrayToAVLTree( value, mid+1, high ); int h1 = ( node->Left == NULL ? -1 : node->Left->Height ); int h2 = ( node->Right == NULL ? -1 : node->Right->Height ); node->Height = 1 + max(h1,h2); return node; }