CODEWITHSUNDEEP
treebinary-search-tree
Harminder
Harminder

Reputation: 2229

constructing a balanced tree

Given the following sorted integers: 1 2 3 4 5 6 7 8. How would you construct a balanced search tree?

I would really appreciate if somebody could explain with without giving code examples.

It is not homework. I'm doing a revision for an exam.

If the values above are put into a balanced tree, should the tree look similar to following?

        5
      4   6
    3      7
   2        8
 1

Upvotes: 1

Views: 271

Answers (2)

Joqus
Joqus

Reputation: 585

You can think on building the from bottom up.

You will have a root. If there is only one element in the tree this is the root. Each element in the root will have a reference to another two node in the tree (binary tree). One for a element bigger than itself and another for a element smaller than itself.

So if you tree has only the number one and you are going to insert number tow, this will be inserted as a leaf, and the reference "bigger than" in the root will point to node 2.

When you insert the value 3 you will have to insert it in the reference "bigger than" of the node 2. But wait, this will make the tree to be unbalanced so you have to correct this. You will have to set the node 2 as the root and point to the node 1 in the "smaller than" and the number three in the "bigger than" reference.

Hope this make you understand it a little better.

The final result depends on the order you insert the elements. But if you insert like 1, 2, 3, 4, 5... The tree should be something like: 

  2
1   3

then 

    3
  2   4
1

and after

    3
  2   4
1       5

and so on. The example when inserting the nodes like this is not so good but if you think in the order: 4, 2, 6, 1, 3, 5 then the result should be something like this:

       4
  2        6
1   3    5

Upvotes: 0

rasmus
rasmus

Reputation: 3216

The simplest way is probably the following:

  • Find the mean value of the list.
  • Partition the integers around the mean where the left side contains smaller numbers and the right side contains larger numbers.
  • Continue by building a tree from each partition recursively.

Since your list of integers is already sorted, you can simply pick the value in the middle to find the mean (and there is no need to move any values around the mean when you partition). You get the subtrees by simply dividing the list in two parts.

The final tree depends on which node you choose as middle. This is one example:

    4
 2     6
1 3   5 7 
          8

Upvotes: 4

Related Questions