Re: insert number in binary tree
- From: Richard Heathfield <rjh@xxxxxxxxxxxxxxx>
- Date: Sun, 07 Oct 2007 16:54:58 +0000
bbbb said:
Hi ,
does anyone know how do we insert numbers in a binary tree?
Any way you like, but I presume you're talking about a simple binary search
tree.
I know the way, but i don't know the correct sequence of the steps?
If this subtree is empty, place the new value *here*. Otherwise, compare
the value to the one already here. If it's lower, try the left subtree,
otherwise try the right subtree.
for ex. if we have the 10 17 25 30 35 39 47 60
Let's start by adding the first node, 10:
10
Now let's add 17. Well, 17 is greater than 10, so let's try the right
subtree. It's empty, so we can store 17 there:
10
\
17
Now 25. Well, it's greater than 10, so we "go right", finding 17. It's
greater than 17, so we go right, finding an empty subtree, so we can fill
it with 25.
10
\
17
\
25
and so on. Since your data are all increasing, we're going to get a long
straggly line rather than a nice bushy tree. We can fix that with any of a
number of balancing algorithms.
For example, we could keep a count of the number of nodes we have, and see
how deeply we must recurse before finding an empty subtree (compared to
the ideal minimum for that number of nodes):
10
Perfectly balanced.
10
\
17
To store two nodes, ceil(log2(2))+1 levels are necessary. Here, we need two
levels, and we have two levels, so that's fine.
10
\
17
\
25
gives us too heavy a right subtree. We can fix this by promoting the right
successor of the root:
17
/ \
10 25
Adding 30 is easy - we're already full, so anything we add can't unbalance
the tree, at least not in a way anyone can fix:
17
/ \
10 25
\
30
But when we add 35, we get a fixable imbalance:
17
/ \
10 25
\
30
\
35
Again, promoting the right successor of the root will fix this:
25
/ \
17 30
/ \
10 35
39 next:
25
/ \
17 30
/ \
10 35
\
39
We now have four levels when we only need three. Promoting the right
successor of the root won't help here, because the root's left subtree has
two nodes and its right subtree three nodes. These are only one apart from
each other, so this isn't where the imbalance is happening. So we balance
each subtree according to the same rule. Left subtree is already balanced,
so we look at the right subtree, which uses three levels instead of two to
store three nodes. We fix this by promoting the right subtree's root's
right successor.
25
/ \
17 35
/ / \
10 30 39
47 next.
25
/ \
17 35
/ / \
10 30 39
\
47
The tree uses four levels, where it could get away with three. In this
case, the root node is unbalanced, so we can get a better tree by
promoting its right successor into its position:
25
/ \
17 30
/ \
10 35
\
39
\
47
30
/ \
25 35
/ \
17 39
/ \
10 47
The root node is now balanced, but its subtrees are not. Recursing in and
applying the same rules, we get:
30
/ \
17 39
/ \ / \
10 25 35 47
Adding 60 doesn't actually unbalance the tree (in a way that we can do
anything about), because before adding it we have a "full" tree, so our
next entry is bound to add a new level whatever value it has:
30
/ \
17 39
/ \ / \
10 25 35 47
\
60
the tree is :
1(35)
2(25) 3(47)
6(17) 4(30) 8(39) 5(60)
7(10)
Yes, that would do it too, but your way you have to know in advance what
numbers you're going to get.
so which is the correct sequence for the number?
There's no such thing as a "correct sequence". Just add 'em as they come
in.
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
.
- Follow-Ups:
- Re: insert number in binary tree
- From: bbbb
- Re: insert number in binary tree
- References:
- insert number in binary tree
- From: bbbb
- insert number in binary tree
- Prev by Date: insert number in binary tree
- Next by Date: Re: insert number in binary tree
- Previous by thread: insert number in binary tree
- Next by thread: Re: insert number in binary tree
- Index(es):
Relevant Pages
|
Loading
