Reputation: 43
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
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
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