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

Program segment for quick sort, Illustrates the program segment for Quick s...

Illustrates the program segment for Quick sort. It uses recursion. Program 1: Quick Sort Quicksort(A,m,n) int A[ ],m,n { int i, j, k; if m { i=m; j=n+1; k

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

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

Multidimensional array in one dimensional array, Q. By giving an example sh...

Q. By giving an example show how multidimensional array can be represented in one the dimensional array.

Write down a module to merge two linked lists, Two linked lists are having ...

Two linked lists are having information of the same type in ascending order. Write down a module to merge them to a single linked list that is sorted merge(struct node *p, stru

What is diffuse illumination, Diffuse Illumination Diffuse illuminatio...

Diffuse Illumination Diffuse illumination means light that comes from all directions not from one particular source. Think about the light of a grey cloudy day as compared to

Algorithm for binary search, Q. Write down the algorithm for binary search....

Q. Write down the algorithm for binary search. Which are the conditions under which sequential search of a list is preferred over the binary search?

Exact analysis of insertion sort, Exact analysis of insertion sort: Let...

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

Deletion of an element from the linked list, A LGORITHM (Deletion of an ele...

A LGORITHM (Deletion of an element from the linked list) Step 1  Begin Step 2  if the list is empty, then element cannot be deleted Step 3  else, if the element to be del

What is ruby, What is Ruby Ruby has numerous simple types, including nu...

What is Ruby Ruby has numerous simple types, including numeric classes such as Integer, Fixnum, Bignum, Float, Big Decimal, Rational, and Complex, textual classes like String,

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