For AVL tree, write C functions to rotate-right, rotate-left,
insert and delete, to
check if a BST is a AVL tree.
struct Node *rightRotate(struct Node *y)
{
struct Node *x = y->left;
struct Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right))+1;
x->height = max(height(x->left),
height(x->right))+1;
// Return new root
return x;
}
struct Node *leftRotate(struct Node *x)
{
struct Node *y = x->right;
struct Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right))+1;
y->height = max(height(y->left),
height(y->right))+1;
// Return new root
return y;
}
struct Node* insert(struct Node* node, int key)
{
/* 1. Perform the normal BST insertion */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys are not allowed in BST
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this ancestor
node to check whether this node became
unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced, then
// there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key >
node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key <
node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) –
height(N->right);
}
Node* deleteNode(Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller
// than the root’s key, then it lies
// in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater
// than the root’s key, then it lies
// in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root’s key, then
// This is the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
Node *temp = root->left ?
root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);
// Copy the inorder successor’s
// data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}
// If the tree had only one node
// then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF
// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 &&
getBalance(root->left) < 0) { root->left =
leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root); // Right Left Case if (balance < -1
&& getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
/* Returns true if binary tree with root as root is height-balanced
which means AVL tree*/
bool isBalanced(struct node *root)
{
int lh; /* for height of left subtree */
int rh; /* for height of right subtree */
/* If tree is empty then return true */
if(root == NULL)
return 1;
/* Get the height of left and right sub trees */
lh = height(root->left);
rh = height(root->right);
if( abs(lh-rh) <= 1 &&
isBalanced(root->left) &&
isBalanced(root->right))
return 1;
/* If we reach here then tree is not height-balanced */
return 0;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* returns maximum of two integers */
int max(int a, int b)
{
return (a >= b)? a: b;
}
For AVL tree, write C functions to rotate-right, rotate-left, insert and delete, to check if a BS...
Please C code for AVL trees -> insert(recursive),height,balance factor,left rotate,right rotate,max and init functions..
AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. Perform insert and delete simulation for each given number below by using the concept of AVL Tree! a. INSERT: +300, +500, +700, +600, +650, +550, +525, +510, +580, +200, +565, +800 b. DELETE: -525, -500, -510, -650, -700 *you are obligated to use predecessor (left subtree's right-most child) for the replacement process
PYTHON QUESTION... Building a Binary Tree with extended Binary Search Tree and AVL tree. Create a class called MyTree with the methods __init__(x), getLeft(), getRight(), getData(), insert(x) and getHeight(). Each child should itself be a MyTree object. The height of a leaf node should be zero. The insert(x) method should return the node that occupies the original node's position in the tree. Create a class called MyBST that extends MyTree. Override the method insert(x) to meet the definitions of a...
True or false? (a) An insertion in an AVL tree with n nodes requires Θ (log(n)) rotations. (b) A set of numbers are inserted into an empty BST in sorted order and inserted into an empty AVL tree in random order. Listing all elements in sorted order from the BST is O (n), while listing them in sorted order from the AVL tree is O (log(n)). (c) If items are inserted into an empty BST in sorted order, then the...
[74, 92, 75, 46, 60, 3, 90, 78, 7]The task here is to show a trace of the operations needed to insert objects with your (list of) keys, one by one, into an initially empty AVL tree with restoration of AVL balance (if necessary) after each insertion.Your submission should have the section heading 'AVL trace' followed by the coded trace of operations: Ixx to insert key xx at the root of the previously empty AVL tree; IxxLyy to insert key...
7. Write the AVL tree code and insert the above numbers. Show the screen shot of the pre-order traversal of the resulting tree. Compare the result with the previous question.
LANGUAGE: C++ Write a class to create the binary tree (insert, delete, search, exit) and display the output using inorder, preorder and postorder tree traversal methods.
There are N numbers in the sequence. Please insert those numbers into an empty AVL tree one by one. After the AVL tree has been constructed: (1) Input: N The sequence of numbers Number which will be deleted from the tree (2) Print out The sequence of the tree by pre-order traversal The sequence of the tree by in-order traversal The sequence of the tree by post-order traversal NEW TREE AFTER DELETING number The sequence of the tree by pre-order...
2. a) Consider the following AVL Tree. 50 / 25 75 10 Insert the following values in the given AVL Tree, one after another, and show the resulting tree after each insertion. You must justify your answer by explaining the rotation operation you performed during insertion. 17 40 10 90 5 100 b) Delete the root of the resulting tree in Question 2.a. Show the resulting AVL Tree. Justify your answer by showing every step during deletion.
Assume the following notation/operations on AVL trees. An empty AVL tree is denoted E. A non-empty AVL tree T has three attributes The key T.key is the root node's key. The left child T.left is Ts left subtree, which is an AVL tree (possibly E). The right child T.right is T's right subtree, which is an AVL tree (possibly E). (a) 5 marsl Write a function RANGECOUNT(T, lo, hi) to count the number of nodes in an AVL tree with...