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
$\begingroup$
$\endgroup$
-
2$\begingroup$ What do you think? $\endgroup$ – Raphael♦ Mar 1 '15 at 23:59
$\begingroup$
$\endgroup$
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).
-
$\begingroup$ so, inserting 3, 3, and 3 using your method would still result in the tree I showed above, correct? $\endgroup$ – STC Mar 1 '15 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$ – Francesco Gramano Mar 1 '15 at 19:46
$\begingroup$
$\endgroup$
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.
