binary search tree

I am trying to learn about binary search trees and I am not getting far. I am looking at this example. can anyone give some insight?

The following names are inserted in the order given, into an initially empty binary search tree.

Ellen,bob,george,angie,frank,david,connie.

Which names will be in the leaves of the completed leaves?
Which names will be in nodes with exactly one child?
Which names insertion will force the first rotation?
Which name will be the lowest unbalanced node at the time of the first rotation?


Help?
Danny

Hmm, BST and AVL(Splay) trees are different beings. A BST is simply an ordered tree, in which for every element in the tree, there will either be an object that precedes it to it's left or no element at all, and an object that succeeds it to it's right, or no element at all. An AVL tree on the other hand, has requirements on the structure of the tree, the difference between the height of the right and left subtrees for any node in the list differ by at most 1.

Your question seems to be addressed to AVL trees, rather than general BST trees, because you are using rotation. Unfortunetely, showing the rotation neccesary to maintain an AVL tree is very hard on a message board like this. That said, after making the AVL tree, no nodes even were needed to be rotated.

Insert Ellen, Ellen becomes root.

Insert Bob, Bob is less than Ellen, move left. Nothing there, insert Bob to left of Ellen.

Insert George, George greater than Ellen, move right. Nothing there, insert George right of Ellen.

Insert Angie, Angie less than Ellen, move left. Angie less than Bob, move left. Nothing there, insert Angie left of Bob.

Insert Frank. Frank greater than Ellen, move right. Frank less than George, move left. Nothing there, insert Frank left of George.

Insert David. David less than Ellen, move left. David less than Bob, move right. Nothing there, insert David left of Bob.

Insert Connie. Connie less than Ellen, move left. Connie greater than Bob, move right. Connie less than David, move left. Nothing there, insert Connie left of David.


Angi, Connie, and Frank are the leaves of tree.

The difference between the heights of any two subtrees of a given node is no more than one, so there were no rotations neccesary.

The lowest unbalanced node in the tree is David, as it has Connie has it's left child, but no right child.

Hope it helps, and I hope I didn't screw it up, further confusing you ;).

Thanks for the information. But what makes one greater or less than the other?

Danny

It normally depends on which one is lexicographically less or greater (the order in which they'd appear in a dictionary).

so i have another question... so far the tree looks like this

********Ellen
*********/\
******Bob George
******/\*****/
*Angie David Frank
******/
**Connie

how do u handle rotations if the next three names were:
Daniel, Christine, and Caroline

since that would make the difference between the heights of any two subtrees of a given node is more than one.

thx

Chandra