4
$\begingroup$

Is it possible to insert a sequence of non-unique elements into an AVL tree?

For example, what is the AVL tree result of inserting 3, 3, and 3 into an initially empty AVL tree?

Is it:

        3
      /   \
     3     3
$\endgroup$
1
  • 2
    $\begingroup$ What do you think? $\endgroup$
    – Raphael
    Mar 1, 2015 at 23:59

2 Answers 2

4
$\begingroup$

A BST (from which the AVL descends) with duplicate keys can have its rotation make nodes with the same key be on both sides of the parent node, in which case, some ambiguity might result. However, you could make your life a whole lot easier and have each node contain a key and the number of times that key had been inserted into the tree, to therefore keep track of successive inserts of successive keys and disambiguate its structure.

You would still insert a node (first by searching for the expected placement for the node) with respect to its key, initialize its count to 0, and towards the end of completing the insert increment that count).

$\endgroup$
2
  • $\begingroup$ so, inserting 3, 3, and 3 using your method would still result in the tree I showed above, correct? $\endgroup$
    – STC
    Mar 1, 2015 at 19:18
  • 1
    $\begingroup$ No, using this method would result in a single node $n = (3, 3)$ representing that entire subtree, where the node's first component is the key and the second component is its count. $\endgroup$ Mar 1, 2015 at 19:46
0
$\begingroup$

After consulting with an EECS TA, I have come to the conclusion that if duplicate values are allowed to be entered in an AVL tree, then adding 3 elements of the same value (e.g. 1,1,1) will result in a tree as shown above, with a parent node equal to both its left and right children.

$\endgroup$
1
  • $\begingroup$ The answer above shows how to deal with it. $\endgroup$
    – Evil
    Jul 9, 2016 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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