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?
3 / \ 3 3
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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).
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.