Yeah, that's wrong.Your code doesn't do an avl tree, it just does a regular bst without any balancing logic, so where a node goes, it stays. The tree looks like this with that sequence of insertions:
Code:3,7,5,4,2,1,6 3 / \ 2 7 / / 1 5 / \ 4 6
Yeah, that's wrong.
Code:3,7,5,4,2,1,6 3 / \ 2 7 / / 1 5 / \ 4 6
As others are stating, an AVL tree is always supposed to be balanced with the exception of during an insertion or deletion. By the end of the insertion or deletion, however, you should have balanced the tree.
1. insert a node
2. check if balanced
3. if not balanced, balance
Thanks for the replies.
“Example isn't another way to teach, it is the only way to teach” Albert Einstein
Take the middle element of the sorted array. This will be the root of the tree. Take everything left of this middle element and construct a balanced tree from it, and make this the left subtree. Same for the right. Recursive implementation is just a few lines.Originally Posted by BoneXXX
If the data is already sorted, there is no need to make a tree out of it. Just do binary search.
Is this for an assignment? If not, you're making things harder than they need to be. The height of ANY balanced tree of N nodes is simply floor(log2(N))+1.
Thats the way I intend to balance my ternary tree code. Adding the logic to balance the tree during every insertion and deletion is just a pain. Of course if the tree is large and unbalanced, you might run out of stack space. Thus iteration with a stack (LIFO) allocated from the heap for your node traversal is in order, rather than the more elegant recursive solution.
My question, however, is this:
Is generating a sorted list from a potentially unbalanced ternary (or even binary) tree of order n, the number of entries? For a binary tree I think the answer is yes, that you only have to visit each node at most three times as you do a depth first traversal. For ternary trees where the sort is in lexigraphical order I think you visit a node at most 4 times.
