Jill Ceke

Greenhorn

Posts: 8

posted 4 years ago

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

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

Jill Ceke

Greenhorn

Posts: 8

posted 4 years ago

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

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

posted 4 years ago

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 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

posted 4 years ago

Please BeForthrightWhenCrossPostingToOtherSites:

http://bd.summit.net/articles/2013/12/11/binary-search-tree-questions-please-help/

http://www.unix.com/showthread.php?s=2ed77561a3be7b519ab41cc38b746fbc&p=302879215#post302879215

http://stackoverflow.com/questions/20510293/basic-and-balance-bst-insertion-node-placement

http://bd.summit.net/articles/2013/12/11/binary-search-tree-questions-please-help/

http://www.unix.com/showthread.php?s=2ed77561a3be7b519ab41cc38b746fbc&p=302879215#post302879215

http://stackoverflow.com/questions/20510293/basic-and-balance-bst-insertion-node-placement

Jill Ceke

Greenhorn

Posts: 8

posted 4 years ago

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

Ulf Dittmer wrote:Please BeForthrightWhenCrossPostingToOtherSites:

http://bd.summit.net/articles/2013/12/11/binary-search-tree-questions-please-help/

http://www.unix.com/showthread.php?s=2ed77561a3be7b519ab41cc38b746fbc&p=302879215#post302879215

http://stackoverflow.com/questions/20510293/basic-and-balance-bst-insertion-node-placement

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

Jill Ceke

Greenhorn

Posts: 8

posted 4 years ago

Thanks a bunch!

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

posted 4 years ago

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

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

posted 3 years ago

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).

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).