#include <stdio.h>
#include<stdlib.h>
struct BSTreeNode
{
int data;
struct BSTreeNode *left;
struct BSTreeNode *right;
int heightOfNode;
};
void InOrder(struct BSTreeNode *root)
{
if(root != NULL)
{
InOrder(root->left);
printf("%d ",root->data);
InOrder(root->right);
}
}
int Treeheight(struct BSTreeNode *root)
{
if (root == NULL)
return 0;
return root->heightOfNode;
}
int max(int a, int b)
{
if(a >= b)
return a;
return b;
}
struct BSTreeNode* GetNode(int data)
{
struct BSTreeNode* temp = (struct BSTreeNode*)
malloc(sizeof(struct BSTreeNode));
temp->data = data;
temp->left = NULL;
temp->right = NULL;
temp->heightOfNode = 1;
return temp;
}
struct BSTreeNode *RightRight(struct BSTreeNode *y)
{
struct BSTreeNode *x = y->left;
struct BSTreeNode *T2 = x->right;
x->right = y;
y->left = T2;
y->heightOfNode = max(Treeheight(y->left), Treeheight(y->right))+1;
x->heightOfNode = max(Treeheight(x->left), Treeheight(x->right))+1;
return x;
}
struct BSTreeNode *LeftLeft(struct BSTreeNode *x)
{
struct BSTreeNode *y = x->right;
struct BSTreeNode *T2 = y->left;
y->left = x;
x->right = T2;
x->heightOfNode = max(Treeheight(x->left), Treeheight(x->right))+1;
y->heightOfNode = max(Treeheight(y->left), Treeheight(y->right))+1;
return y;
}
int getBalanceFactor(struct BSTreeNode *root)
{
if (root == NULL)
return 0;
return Treeheight(root->left) - Treeheight(root->right);
}
struct BSTreeNode* AVLInsert(struct BSTreeNode* node, int key)
{
if (node == NULL)
return(GetNode(key));
if (key < node->data)
node->left = AVLInsert(node->left, key);
else if (key > node->data)
node->right = AVLInsert(node->right, key);
else
return node;
node->heightOfNode = 1 + max(Treeheight(node->left),
Treeheight(node->right));
int balancefactor = getBalanceFactor(node);
if (balancefactor > 1 && key < node->left->data)
return RightRight(node);
if (balancefactor < -1 && key > node->right->data)
return LeftLeft(node);
if (balancefactor > 1 && key > node->left->data)
{
node->left = LeftLeft(node->left);
return RightRight(node);
}
if (balancefactor < -1 && key < node->right->data)
{
node->right = RightRight(node->right);
return LeftLeft(node);
}
return node;
}
int main()
{
struct BSTreeNode *root = NULL;
root = AVLInsert(root, 190);
root = AVLInsert(root, 200);
root = AVLInsert(root, 130);
root = AVLInsert(root, 840);
root = AVLInsert(root, 500);
root = AVLInsert(root, 225);
InOrder(root);
return 0;
}
==============================================
SEE OUTPUT
PLEASE COMMENT if there is any concern.
======================================================
Please C code for AVL trees -> insert(recursive),height,balance factor,left rotate,right rotate,max and init functions..
For AVL tree, write C functions to rotate-right, rotate-left, insert and delete, to check if a BST is a AVL tree.
just need to answer the second question 3 AVL Trees 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 T's 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) [3 marks] Describe an alternative version of the RANGECOUNT(T,...
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...
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 T’s 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 marks] Write a function RangeCount(T, lo, hi) to count the number of nodes in an...
[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...
class AVLTree The following functions are the minimum requirements for the AVL class. You can add any function from Assignment 2 to this class. You should modify the BSTree insert function so that the tree remains balanced after each insertion. Required Public Member Functions void insert(const string &): Insert an item to the binary search tree and perform rotation if necessary. int balanceFactor(Node*): Return the balance factor of a given node. void printBalanceFactors(): Traverse and print the tree in inorder...
java AVL tree a). What are the conditions that must exist in a binary tree for calling the left and the right rotation? b). What is the smallest height that a tree of 1000 nodes can be? What is the biggest? Please be very specific, thank you.
I need help to write this code in C++, I am struggling to find max node's parent's right child and max node's left child. Node* maxValueNode(Node* node) { Node* current = node; while (current && current->right != NULL) current = current->right; return current; } void deleteNode(BST* tree, Node* node, Node* parent) { //TODO - follow the lecture pseudocode to write the deleteNode function // - returns true if the value was deleted, false if not // - don't forget to...
Having code issues wth my C++ program. My program checks if two binary trees are similar and if they're not they return false. My program is return true with different binary trees. Could use some help thanks #include <iostream> #include <string> using namespace std; //Struct of Nodes struct BinarySearchTree { int data; BinarySearchTree *left; BinarySearchTree *right; }; // Inserting nodes into BST BinarySearchTree* insert( BinarySearchTree* node, int val) { if (node == NULL) { BinarySearchTree *newNode = new BinarySearchTree(); newNode->data...
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...