CODEWITHSUNDEEP
data-structuresbinary-tree
oneiros
oneiros

Reputation: 3568

Why is it important that a binary tree be balanced?

Why is it important that a binary tree be balanced

Upvotes: 12

Views: 15895

Answers (5)

Sahan Dissanayaka
Sahan Dissanayaka

Reputation: 621

As we know that most of the operations on Binary Search Trees proportional to height of the Tree, So it is desirable to keep height small. It ensure that search time strict to O(log(n)) of complexity.

Rather than that most of the Tree Balancing Techniques available applies more to trees which are perfectly full or close to being perfectly balanced.

At the end of the end you need the simplicity over your tree and go for best binary trees like red-black tree or avl

Upvotes: 0

Mohan
Mohan

Reputation: 1955

The balance of a binary tree is governed by the property called skewness. If a tree is more skewed, then the time complexity to access an element of a the binary tree increases. Say a tree

                1
               / \
              2   3
              \    \
               7    4
                     \
                      5
                       \
                        6

The above is also a binary tree, but right skewed. It has 7 elements, so an ideal binary tree require O(log 7) = 3 lookups. But you need to go one more level deep = 4 lookups in worst case. So the skewness here is a constant 1. But consider if the tree has thousands of nodes. The skewness will be even more considerable in that case. So it is important to keep the binary tree balanced.

But again the skewness is the topic of debate as the probablity analysis of a random binary tree shows that the average depth of a random binary tree with n elements is 4.3 log n . So it is really the matter of balancing vs the skewness.

One more interesting thing, computer scientists have even found an advantage in the skewness and proposed a skewed datastructure called skew heap

Upvotes: 8

RoneRackal
RoneRackal

Reputation: 1233

An extremely unbalanced tree, for example a tree where all nodes are linked to the left, means you still search through every single node before finding the last one, which is not the point of a tree at all and has no benefit over a linked list. Balancing the tree makes for better search times O(log(n)) as opposed to O(n).

Upvotes: 1

perreal
perreal

Reputation: 97938

To ensure log(n) search time, you need to divide the total number of down level nodes by 2 at each branch. For example, if you have a linear tree, never branching from root to the leaf node, then the search time will be linear as in a linked list.

Upvotes: 4

Danica
Danica

Reputation: 28846

Imagine a tree that looks like this:

  A
   \
    B
     \
      C
       \
        D
         \
          E

This is a valid binary tree, but now most operations are O(n) instead of O(lg n).

Upvotes: 11

Related Questions