Sign in to follow this  

general question about binary trees

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

just a general question out of curiosity, is it possible to have only a RIGHT sub-tree? like, can a tree have just a right sub-tree, or is it that you can't have a right sub-tree without first having a left sub tree? hope that's a valid question that makes sense, thanks.

Share this post


Link to post
Share on other sites
No can't say i understand you. Are you meaning that you want only one right sub-node for each node? ...that wouldn't be a tree but rather a list, no.
I think you have to elaborate a bit further [smile]

EDIT: Ok, i'm oficially lost...

Share this post


Link to post
Share on other sites
It is possible, depending on how you build the tree (as Simian mentioned already). This is not a good thing, though, as it generates the absolute worst-case performance for a binary tree (it's basically a linear list, as Android_s mentioned).

Why is is so bad? The whole idea behind a binary tree is that which each decision, you divide the problem space by 2: every time to go to either the right or left node, you have effectively ignored all those on the other side. This makes searching rather fast. In the case you mention, you're never ignoring any nodes, just moving on to the next one.

This situation is avoided either by carefully building the tree (by sorting the nodes before you add them), or by using a 'self-balancing' binary tree. This is a binary tree that alters itself everytime a node changes in an attempt to keep an equal number of nodes on each side. Lots of info on this on the web.

Enough? Too much? Confused? Good!

Share this post


Link to post
Share on other sites
Having unbalanced nodes is a part of every type of tree data structure. Consider the case where you only have two nodes for example. The head node can only have one child.

However, there is a certain tree type called an AA-Tree, in which you can never have a left child without having a right child. In this case, it merely limits the possible combinations of tree structures to those which are not left-heavy.
All other types of trees allow more than one representation for the unbalanced cases.

Share this post


Link to post
Share on other sites

This topic is 4686 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this