1
$\begingroup$

I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?

Let $A$ be the set of integers. Given any set $A$, it's possible to create an avl tree corresponding to the given set of numbers.

Is there any way to prove or work out the above statement? I appreciate your answers.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Notice that the numbers themselves do not matter. You statement is equivalent to asking if, for every positive integer $n$ there exists an AVL tree with $n$ nodes. You can assign numbers to nodes in a symmetric DFS order. $\endgroup$ – Steven Jan 20 at 11:07
  • $\begingroup$ Given the question precisely as stated, the answer is a clear "no". It's trivial to define infinite sets (e.g., "integers", "positive integers", "even integers", "primes", etc.) and although we can imagine infinite trees, we can't actually construct them. $\endgroup$ – Jerry Coffin Jan 20 at 20:37
4
$\begingroup$

Your question is not the right one.

An AVL tree is a binary tree that has additional properties. First it is a search tree, which means we can easily find each number in the tree. Second it is balanced, meaning that there are no leafs very far form the root. (Formal definitions on request.)

Assume you have a set of $n$ numbers in advance, and an arbitrary "empty" binary tree with $n$ nodes, you can make the tree into a search tree putting the nodes at a well defined position. So, If you can find an empty tree with AVL structure it is no problem to fill it with the values. And indeed, a completely balanced binary tree, adding nodes level by level, satisfies the requirement of AVL trees.

The proper question is: "can we keep a binary tree in AVL form when the values are added and deleted one by one". When we can do this we have build a quite efficient data structure for sets of values.

Improve this answer
$\endgroup$
4
$\begingroup$

AVL trees are a kind of binary search trees. As such, they implement the following operations, among else:

  • Initialize an empty tree.
  • Add a value to the tree.
  • Remove a value from the tree.
  • Search a value in the tree.

Try to use some of these operations to answer your question.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.