Register
It is currently Wed Dec 17, 2014 7:18 pm

Binary search trees insertion node placement question


All times are UTC - 6 hours


Post new topic Reply to topic  [ 2 posts ] 
Author Message
 PostPosted: Wed Dec 11, 2013 8:59 am   

Joined: Sun Dec 01, 2013 9:47 pm
Posts: 2
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.

Image

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

Image

insert 11

Image


Top
 Profile  
 PostPosted: Wed Dec 11, 2013 5:25 pm   
User avatar

Joined: Wed Jun 08, 2011 8:27 am
Posts: 189
Location: outer Shpongolia
Jill Ceke wrote:
[...] 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 can see node 3 as the root of an extensible subtree that can get two children.
4 is added to the right child of this subtree because it's greater than the subtree's root (parent), which is 3.

Jill Ceke wrote:
[...] Inserting the fourth node, 7, went down through 18 instead of 3. Is there a particular reason why?

7 is greater than 5, so it goes to the right child, and 7 is less than 18, so it goes to node 18 subtree's left child.

Jill Ceke wrote:
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?

No, at first 11 belongs to the left child because it's less than its parent, which is 18.

Then a right rotation occurs to balance the subtree:
The left child becomes the parent which becomes the right child, and the left leaf becomes the left child.


P.S.: Are you really using a binary tree implementation in bash(1)? How come you need it?


Top
 Profile  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: Bing [Bot] and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Jump to:  


BashScripts | Promote Your Page Too
Powered by phpBB © 2011 phpBB Group
© 2003 - 2011 USA LINUX USERS GROUP