programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Binary search trees questions

Jill Ceke
Greenhorn
Posts: 8
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
Where did you get that insert 11 diagram from? It does not look correct to me.

Jill Ceke
Greenhorn
Posts: 8
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
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.

Ulf Dittmer
Rancher
Posts: 42972
73

Jill Ceke
Greenhorn
Posts: 8

Sorry, I'll indicate next time I cross post.

Jill Ceke
Greenhorn
Posts: 8
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
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.

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