Answer to Question #271829 in Algorithms for kalpana T

Question

Let us consider you are going to be create a AVL tree by inserting one by one up to 15 nodes with the help of Random number generation function. At each node, after insertion you should maintain the tree as balanced one. Sketch the Avl tree from the first node insertion to last 15^th node insertion step by step. Then you have start to delete operation with 5^th,10th and 15^th input of inserted node. You have to follow the given details mentioned below for node input.

Sl.No

Student’s Roll Number

Range of Input

Insertion

Deletion

1

201IT101 - 201IT117

1 - 75

Totally 15 randomized numbers from the Specified range

Delete the 5^th , 10^th and 15^th randomized input number when inserted.

2

201IT118 - 201IT134

76 - 150

3

201IT135 - 201IT151

151 - 225

4

201IT152 - 201IT168

226 - 300

5

201IT169 - 201IT216

301 - 375

6

201IT218 - 201IT234

376 - 450

7

201IT235 - 201IT251

451 - 525

8

201IT252 - 201IT269

526 – 600

Program ( 5 Marks)

Tree Structure step by step (15 Marks) for 15 node insertion.

Answer 1

A self-balancing tree is a binary search tree that balances the height after insertion and deletion according to some balancing rules.

The worst-case time complexity of a BST is a function of the height of the tree. Specifically, the longest path from the root of the tree to a node. For a BST with N nodes, let's say that that every node has only zero or one child. Therefore its height equals N, and the search time in the worst case is O(N). So our main goal in a BST is to keep the maximum height close to log(N).

The balance factor of node N is height(right(N)) – height(left(N)). In an AVL Tree, the balance factor of a node could be only one of 1, 0, or -1 values.

The AVL Tree checks the balance factor of its nodes after the insertion or deletion of a node. If the balance factor of a node is greater than one or less than -1, the tree rebalances itself.

There are two operations to rebalance a tree:

• right rotation and
• left rotation.