Thread: binary search tree

  1. #1
    unregistered
    Guest

    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

  2. #2
    geek SilentStrike's Avatar
    Join Date
    Aug 2001
    Location
    NJ
    Posts
    1,141
    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 .
    Prove you can code in C++ or C# at TopCoder, referrer rrenaud
    Read my livejournal

  3. #3
    Unregistered
    Guest

    less or greater

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

    Danny

  4. #4
    of Zen Hall zen's Avatar
    Join Date
    Aug 2001
    Posts
    1,007
    It normally depends on which one is lexicographically less or greater (the order in which they'd appear in a dictionary).
    zen

  5. #5
    Chandra
    Guest
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. BST (Binary search tree)
    By praethorian in forum C++ Programming
    Replies: 3
    Last Post: 11-13-2005, 09:11 AM
  3. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 05:15 PM
  4. binary search and search using binary tree
    By Micko in forum C++ Programming
    Replies: 9
    Last Post: 03-18-2004, 10:18 AM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM