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

Undirected graph and adjacency matrix, Q. Consider the specification writte...

Q. Consider the specification written below of a graph G V(G ) = {1,2,3,4} E(G ) = {(1,2), (1,3), (3,3), (3,4), (4,1)} (i)        Draw the undirected graph. (

Circular linked list, In a circular linked list There is no beginning a...

In a circular linked list There is no beginning and no end.

Insert an element after an element pointed by some pointer, Consider a link...

Consider a linked list of n elements. What is the time taken to insert an element after an element pointed by some pointer? O (1)

Enumerate the types in ruby, Enumerate the Types in Ruby Ruby is a pure...

Enumerate the Types in Ruby Ruby is a pure object-oriented language, meaning that all types in Ruby are classes, and each value in a Ruby program is an instance of a class. Thi

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 to insert element to a max-heap sequentially, Q. Write  down the ...

Q. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to

Mathematical-model with a collection of operations, A mathematical-model wi...

A mathematical-model with a collection of operations described on that model is known as??? Abstract Data Type

Algorithmic implementation of multiple stacks, So far, we now have been con...

So far, we now have been concerned only with the representation of single stack. What happens while a data representation is required for several stacks? Let us consider an array X

Decision tree - id3 algorithm, Decision Tree - ID3 algorithm: Imagine ...

Decision Tree - ID3 algorithm: Imagine you only ever do one of the following four things for any weekend:   go shopping   watch a movie   play tennis   just

User-specified memory location, You need to implement a function which will...

You need to implement a function which will write out a given user-specified memory location to disk in base 10. That means that you have to convert the large number data structure

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