CODEWITHSUNDEEP
data-structuresbinary-search-treeavl-tree
Lovely
Lovely

Reputation: 43

Difference between complete binary search tree and AVL tree?

Is there any difference between the complete binary search tree and an AVL tree? Give an example.

Searched on google but found this. not much helpful

Upvotes: 1

Views: 5395

Answers (2)

templatetypedef
templatetypedef

Reputation: 373492

Every complete binary tree is an AVL tree, but not necessarily the other way around.

A complete binary tree is one where every layer except possibly the last is completely filled in. An AVL tree is one where every node's children are AVL trees whose heights differ by at most one. The maximally skewed AVL trees are the Fibonacci trees, which generally aren't complete trees. Here's an example of a tree that's an AVL tree and not a complete binary tree:

          .
        /    \
     .         .
    / \       / \
   .   .     .   .
      /     /   / \
     .     .   .   .
                  /
                 .

Upvotes: 3

user11554589
user11554589

Reputation:

AVL tree and Binary search tree are both same but AVL tree has a constraint that the difference between the height of left sub tree and right sub tree should either be 0, 1 or -1.

If any binary search tree meet these conditions it will be called as AVL tree.

Binary search tree + HEIGHT CONDITION is an AVL tree.

Refer: Introduction to Algorithms by Cormen https://books.google.co.in/books..

Upvotes: 1

Related Questions