Avl trees, Data Structure & Algorithms

Assignment Help:

An AVL tree is a binary search tree that has the given properties:

  • The sub-tree of each of the node differs in height through at most one.
  • Each sub tree will be an AVL tree.

Figure illustrated an AVL tree.

2083_AVL TREES.jpg

Figure: Balance requirement for AVL tree: the left & right sub tree differ by at most one in height

AVL stands for the names of G.M. Adelson - Velskii & E.M. Landis, two Russian mathematicians, who came up along with this method of keeping the tree balanced.

An AVL tree is a binary search tree that has the balance property and additionally to its key, each of the node stores an additional piece of information: the current balance of its subtree. The three possibilities are following:

  • Left - HIGH (balance factor -1)

The left child contain a height which is greater than the right child by 1.

  • BALANCED (balance factor 0)

 Both of children have the same height

  • RIGHT - HIGH (balance factor +1)

The right child contains a height that is greater by 1.

An AVL tree that remains balanced guarantees O(log n) search time, even into the worst case. Here, n refer to the number of nodes. The AVL data structure gain this property by placing limitation on the difference in heights among the sub- trees of given node and rebalancing the tree even if it violates these limitation.


Related Discussions:- Avl trees

Files structures, The structures of files vary from operating system to ope...

The structures of files vary from operating system to operating system. In this unit, we will discuss the fundamentals of file structures with the generic file organisations. A

Define about the class invariant, Define about the class invariant A cl...

Define about the class invariant A class invariant may not be true during execution of a public operation though it should be true between executions of public operations. For

The various ways in which lc code can be accessed, Problem Your LC code...

Problem Your LC code is stored in a memory location as shown and the variable name is LC                  LC Memory address       Content(LC code)

Arrays, This unit discussed about data structure called Arrays. The easiest...

This unit discussed about data structure called Arrays. The easiest form of array is a one-dimensional array which may be described as a finite ordered set of homogeneous elements

Data structures, 1.  You are required to hand in both a hard copy and an el...

1.  You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.  2.  You

Write an algorithm to input number of passengers travelling, There are ten ...

There are ten stations on a railway line: Train travels in both directions (i.e. from 1 to 10 and then from 10 to 1).  Fare between each station is $2. A passenger input

Explain the representations of graph, Explain the representations of graph....

Explain the representations of graph. The different ways of representing a graph is: Adjacency list representation : This representation of graph having of an array Adj of

Algorithm, Example of worse case of time

Example of worse case of time

Importance of game theory to decisions, Question: (a) Discuss the impor...

Question: (a) Discuss the importance of game theory to decisions. (b) Explain the following: (i) saddle point, (ii) two-person zero-sum game. (c) Two leading ?rms, ABC Ltd a

Write a function that performs the integer mod function, Write a function t...

Write a function that performs the integer mod function. Given the previous functions you have implemented already, this one should be a piece of cake. This function will find the

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd