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.
`Hey,
Note: If you have any queries related the answer please do comment. I would be very happy to resolve all your queries.
#include<iostream>
#include<cstdio>
#include<sstream>
#include<algorithm>
#define pow2(n) (1 << (n))
using namespace std;
struct avl {
int d;
struct avl *l;
struct avl *r;
}*r;
class avl_tree {
public:
int height(avl *);
int difference(avl *);
avl *rr_rotat(avl *);
avl *ll_rotat(avl *);
avl *lr_rotat(avl*);
avl *rl_rotat(avl *);
avl * balance(avl *);
avl * insert(avl*, int);
void show(avl*, int);
void inorder(avl *);
void preorder(avl *);
void postorder(avl*);
avl_tree() {
r = NULL;
}
};
int avl_tree::height(avl *t) {
int h = 0;
if (t != NULL) {
int l_height = height(t->l);
int r_height = height(t->r);
int max_height = max(l_height, r_height);
h = max_height + 1;
}
return h;
}
int avl_tree::difference(avl *t) {
int l_height = height(t->l);
int r_height = height(t->r);
int b_factor = l_height - r_height;
return b_factor;
}
avl *avl_tree::rr_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = t->l;
t->l = parent;
return t;
}
avl *avl_tree::ll_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = t->r;
t->r = parent;
return t;
}
avl *avl_tree::lr_rotat(avl *parent) {
avl *t;
t = parent->l;
parent->l = rr_rotat(t);
return ll_rotat(parent);
}
avl *avl_tree::rl_rotat(avl *parent) {
avl *t;
t = parent->r;
parent->r = ll_rotat(t);
return rr_rotat(parent);
}
avl *avl_tree::balance(avl *t) {
int bal_factor = difference(t);
if (bal_factor > 1) {
if (difference(t->l) > 0)
t = ll_rotat(t);
else
t = lr_rotat(t);
} else if (bal_factor < -1) {
if (difference(t->r) > 0)
t = rl_rotat(t);
else
t = rr_rotat(t);
}
return t;
}
avl *avl_tree::insert(avl *r, int v) {
if (r == NULL) {
r = new avl;
r->d = v;
r->l = NULL;
r->r = NULL;
return r;
} else if (v< r->d) {
r->l = insert(r->l, v);
r = balance(r);
} else if (v >= r->d) {
r->r = insert(r->r, v);
r = balance(r);
} return r;
}
void avl_tree::show(avl *p, int l) {
int i;
if (p != NULL) {
show(p->r, l+ 1);
cout<<" ";
if (p == r)
cout << "Root -> ";
for (i = 0; i < l&& p != r; i++)
cout << " ";
cout << p->d;
show(p->l, l + 1);
}
}
void avl_tree::inorder(avl *t) {
if (t == NULL)
return;
inorder(t->l);
cout << t->d << " ";
inorder(t->r);
}
void avl_tree::preorder(avl *t) {
if (t == NULL)
return;
cout << t->d << " ";
preorder(t->l);
preorder(t->r);
}
void avl_tree::postorder(avl *t) {
if (t == NULL)
return;
postorder(t ->l);
postorder(t ->r);
cout << t->d << " ";
}
int main() {
int c, i;
avl_tree avl;
r = avl.insert(r, 100);
r = avl.insert(r, 200);
r = avl.insert(r, 150);
r = avl.insert(r, 170);
r = avl.insert(r, 165);
r = avl.insert(r, 180);
r = avl.insert(r, 220);
r = avl.insert(r, 163);
r = avl.insert(r, 164);
cout << "Preorder Traversal:" << endl;
avl.preorder(r);
return 0;
}
Kindly revert for any queries
Thanks.
7. Write the AVL tree code and insert the above numbers. Show the screen shot of...
1. (a) Given the following numbers in the given order, show the AVL tree. Show the steps as you do any rotations. 100, 200, 150, 170, 165, 180, 220, 163, 164 (b) Show the pre-order traversal of this AVL tree. (c) (JAVA) 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.
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...
Suppose we insert the numbers 4,5,6,7, and 8 into and AVL tree in that order. Then we traverse the tree via a post-order traversal and print the number at each node. In which order would the numbers print?
Consider the AVL Tree below. Use the AVL Tree Insertion algorithm to add 0017 to the tree. List the nodes of the resulting tree in pre-order traversal order separated by one blank character. For example, the tree below can be described in the above format as: 50 33 80 7785 0050 1 2 0033 0080 1 0077 0085
Consider the AVL Tree below. Use the AVL Tree Deletion algorithm to delete 0033 from the tree. List the nodes of the resulting tree in pre-order traversal order separated by one blank character. For example, the tree below can be described in the above format as: 50 33 77 60 3 0050 0033 0077 1 0060
Please show rotation and balancing factors 1) Insert 13,10,15,5,11,16,4,6,7 in an AVL Tree 2) Insert 43,18,22,9,21,6,8 in an AVL Tree 3) Insert 14, 4, 21, 3, 9, 15, 28, 2, 7, 10, 18, 26, 35 in an AVL Tree. Also, Remove 2, 3, 10, 18 from the AVL Tree.
AVL Tree Initial status is empty. Insert 50, 25, 10, 5, 7, 3, 30, 20, 8, 15 into this AVL tree in order. Draw every status of the tree Question 3: AVL Tree Initial status is empty. Insert 50, 25, 10, 5, 7, 3, 30, 20, 8, 15 into this AVL tree in order. Draw every status of the tree
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.
Consider the AVL Tree built by inserting the following sequence of integers, one at a time: 5, 2, 8, 7,9 Then we insert 11. After we insert 11, before we perform any necessary rotations, is the tree balanced? And if not, which is the root of the lowest imbalanced subtree? (a) None, since the tree is already balanced after inserting 11. (b) The node containing 5. (c) The node containing 8. (d) The node containing 11. (e) The node containing...
Insert numbers 4, 8, 7, 9, 0 in order into a tree and ensure that the resulting tree is a binary search tree.