• Post Reply Bookmark Topic Watch Topic
  • New Topic

Binary search trees questions  RSS feed

 
Jill Ceke
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
Campbell Ritchie
Marshal
Posts: 56536
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Where did you get that insert 11 diagram from? It does not look correct to me.
 
Jill Ceke
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell Ritchie wrote:Where did you get that insert 11 diagram from? It does not look correct to me.


I used these two web binary tree web applets. I'm sorry I meant to clarify that the very top diagram is for reg binary search trees, and the bottom ones are for AVL trees. Even with the top one, I still don't get
how the insertion of 4 isn't on the left side of parent instead of the right side.

http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html
http://www.qmatica.com/DataStructures/Trees/AVL/AVLTree.html
 
Tyson Lindner
Ranch Hand
Posts: 211
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Jill Ceke wrote:
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?


Its bigger than 3.

The lower goes to the left, the higher to the right, starting from the top.

11 is bigger than 5 but less than 18, so it becomes a new parent, and 18 moves the right of 11 since its bigger.
 
Jill Ceke
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tyson Lindner wrote:
Jill Ceke wrote:
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?


Its bigger than 3.

The lower goes to the left, the higher to the right, starting from the top.

11 is bigger than 5 but less than 18, so it becomes a new parent, and 18 moves the right of 11 since its bigger.


Thanks a bunch!
 
Piet Souris
Master Rancher
Posts: 2044
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Tyson Lindner wrote:Its bigger than 3.

The lower goes to the left, the higher to the right, starting from the top.

11 is bigger than 5 but less than 18, so it becomes a new parent, and 18 moves the right of 11 since its bigger.

That is not completely true.
In fact, since 11 < 18, it goes to the left of 18, and since it iss bigger than 7, it goes to the right of 7.
So, 11 becomes a right child node of 7.

However, if that would be all, then we end up with an unbalanced tree. We have a branch (5 - 3) that is two nodes long,
and a branch (5 - 18 - 7 - 11) that is 4 nodes long. A TreeSet works efficient if all branches are about equal in length.
So what happens next here, is that by replacing node 18 by node 11, we get a more balanced Tree.
That happens, and that is why we see node 11 ending up as parent of node 18.
See Wikipedia for more information about optimising Binary Trees.

Try the following example:

create a TreeSet<Integer>, and add, in this sequence, the integers 1, 2, 3, ..., 8.
Then look at the result.

Greetz,
Piet
 
Matthew Brown
Bartender
Posts: 4568
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:See Wikipedia for more information about optimising Binary Trees.


In particular, you can look for "red-black binary trees", which are one approach to guaranteeing the tree is balanced (it's what TreeMap uses, according to java.util.TreeMap).
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!