CODEWITHSUNDEEP
algorithmtree
Dejell
Dejell

Reputation: 14317

Why are we trying to keep trees balanced

I see many questions that are talking about balanced tree.

For instance R-Tree are better than KD-Tree as they are balanced.

What is the advantage of using a balanced tree over a non-balanced tree?

Upvotes: 2

Views: 139

Answers (2)

Imre Kerr
Imre Kerr

Reputation: 2428

Searching this tree

O
 \
  O
   \
    O
     \
      O
       \
        O
         \
          O
           \
            O

Is going to take Θ(N) time. Searching this tree

     O
   /   \
  O     O
 / \   / \
O   O O   O

Is going to take Θ(logN) time. Since search time is proportional to the height of the tree.

Upvotes: 9

Oded
Oded

Reputation: 498952

It ensures minimum span for the average search.

If your tree isn't balanced, some searches will take longer than others. In the worst case, O(n).

Upvotes: 2

Related Questions