Results 1 to 4 of 4
Like Tree1Likes
  • 1 Post By Jill Ceke

Thread: Hi, I'm new and have a question about binary search trees and avl trees

  1. #1
    Jill Ceke is offline Member
    Join Date
    Dec 2013
    Posts
    2
    Rep Power
    0

    Default Hi, I'm new and have a question about binary search trees and avl trees

    I have some questions about certain placement of child nodes since I'm just learning BSTs and it's quite confusing even after reading some sources and doing some online insertion applets. Let's say I want to add nodes 5,7,3,4 to an empty basic BST.



    Ok I understand that the left child must be less than the parent AND less than or equal to the right child from that same parent. I follow it until we add the 4 node. How do we determine that the insertion of 4 goes to the bottom right leaf position of 3 instead of the bottom left leaf position? Also, doing a AVL insertion of nodes 5,18,3,7,11 yielded some surprising position placements. Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why? Assuming that is the correct way, inserting 11 would switch the 11 and 18 spots, but wouldn't having 18 as the parent node, 7 as left child, and 11 as right child adhere to the principle of left child smaller than parent and smaller or equal to right child? I'm confused! I would appreciate any help. Thank you!

    insert 7



    insert 11


  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,041
    Rep Power
    10

    Default Re: Hi, I'm new and have a question about binary search trees and avl trees

    Quote Originally Posted by Jill Ceke View Post
    Ok I understand that the left child must be less than the parent AND less than or equal to the right child from that same parent.
    The way it fits in my brain is a little more basic: everything to the left of a particular node is less than that node. Everything to the right of a node is greater than that particular node. Keep that in mind for the rest of your questions.

    Quote Originally Posted by Jill Ceke View Post
    I follow it until we add the 4 node. How do we determine that the insertion of 4 goes to the bottom right leaf position of 3 instead of the bottom left leaf position?
    You have a tree that consists of a 5 with a left child of 3 (because it's smaller than 5) and a right child of 7 (because it's greater than 5). You want to insert a 4, so you look at the 5. Since 4 is less than 5, you know it has to go on the left side of it. Now you look at the 3. Since 4 is greater than 3, you know it has to go on the right side of 3.


    Quote Originally Posted by Jill Ceke View Post
    Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why?
    Again, because 7 is greater than 5, it has to be on its right side.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    Jill Ceke is offline Member
    Join Date
    Dec 2013
    Posts
    2
    Rep Power
    0

    Default Re: Hi, I'm new and have a question about binary search trees and avl trees

    Quote Originally Posted by KevinWorkman View Post
    The way it fits in my brain is a little more basic: everything to the left of a particular node is less than that node. Everything to the right of a node is greater than that particular node. Keep that in mind for the rest of your questions.



    You have a tree that consists of a 5 with a left child of 3 (because it's smaller than 5) and a right child of 7 (because it's greater than 5). You want to insert a 4, so you look at the 5. Since 4 is less than 5, you know it has to go on the left side of it. Now you look at the 3. Since 4 is greater than 3, you know it has to go on the right side of 3.



    Again, because 7 is greater than 5, it has to be on its right side.

    OMG, I get it. Sometimes the best explanation is the simplest one. Thank you so much~
    KevinWorkman likes this.

  4. #4
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    4,041
    Rep Power
    10

    Default Re: Hi, I'm new and have a question about binary search trees and avl trees

    No problem. Glad I could help!
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

Similar Threads

  1. Binary Search Trees
    By kraigballa in forum New To Java
    Replies: 2
    Last Post: 04-10-2012, 05:31 PM
  2. Binary Search Trees - Weighting and Recursion
    By CeciliaP in forum New To Java
    Replies: 1
    Last Post: 03-28-2012, 10:32 AM
  3. Replies: 0
    Last Post: 10-20-2011, 07:22 PM
  4. Replies: 2
    Last Post: 10-20-2011, 12:35 AM
  5. Tutorial on Binary Search Trees
    By JordashTalon in forum New To Java
    Replies: 3
    Last Post: 03-18-2009, 04:51 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •