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

Graph traversal schemes, Various graph traversal schemes Graph Traversa...

Various graph traversal schemes Graph Traversal Scheme. In many problems we wish to investigate all the vertices in a graph in some systematic order. In graph we often do no

Logic circuits, the voltage wave forms are applied at the inputs of an EX-O...

the voltage wave forms are applied at the inputs of an EX-OR gate. determine the output wave form

What are the advantages of using assertions, Using Assertions When writ...

Using Assertions When writing code, programmer must state pre- and subtle post conditions for public operations, state class invariants and insert unreachable code assertions a

Technique for direct search, Technique for direct search is    Hashing ...

Technique for direct search is    Hashing is the used for direct search.

The # of times an algorithm executes, for(int i = 0; i for (int j = n -...

for(int i = 0; i for (int j = n - 1; j >= i ; j--){ System.out.println(i+ " " + j);

Multiple queue, What is multiple queue and explain them

What is multiple queue and explain them

Define minimum spanning tree, Define Minimum Spanning Tree A minimum sp...

Define Minimum Spanning Tree A minimum spanning tree of a weighted linked graph is its spanning tree of the smallest weight, where the weight of a tree is explained as the sum

SORTING ALGORIthm, the deference between insertion,selection and bubble sor...

the deference between insertion,selection and bubble sort

Breadth first search, While BFS is applied, the vertices of the graph are d...

While BFS is applied, the vertices of the graph are divided into two categories. The vertices, that are visited as part of the search & those vertices that are not visited as part

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