Binary Tree:
A
Tree in which each node has a degree of atmost 2. i.e. it can have either 0,1
or 2 children.
Here,
leaves are H, I, J. Except these, remaining internal nodes has atmost 2 nodes
as their child.
Full Binary tree:
Every
node should have exactly 2 nodes except the leaves. It is also called as Strict Binary Tree or 2- Binary Tree or Proper Binary Tree.
Complete Binary Tree:
It
is a binary tree in which every level (except possibly the last) is completely
filled, and all nodes are as far left as possible.
The above 4 fig’s are Complete Binary Trees.
Fig1 fig2 fig3
fig
4 
fig
5
These are not complete trees as in
fig1 at level 1, the 0 node has no children. In fig 2, nodes 2, 5, 9 doesn’t
have left child. For a tree to be complete tree, right child is not necessary
but left child is must if right child is present incase of last level. For fig
3, the node 0 doesn’t have a left child.same as for fig 4 and fig 5.
Ordered Binary Tree :
It
is a Binary Tree in which all the elements are arranged in an order i.e. For a
node, All elements of left sub-tree should be smaller than the node and all
elements of right sub-tree should be larger than the node.
In the above fig, Every node has
smaller element as left child and larger element as right child.
·
An Ordered Tree may or may not be balanced. It may have time complexity of
O(n) or O(logn).
In the above Tree, we see that
even though it is an Ordered Tree, it is not balanced. For adding,deleting and
Searching operations, it has time complexity of O(n) same as linked list.
Balanced Binary Tree:
It is a Binary tree in which the
elements are ordered and no leaf is at “much greater” depth than
any other leaf. It will have time complxity of O(logn).
Perfectly balanced binary tree:
It is a Balanced binary tree in
which the difference in the left and right tree nodes’ count of any
node is at most one.
In
the given fig, the left binary tree is ordered whereas right binary tree is
ordered and balanced.
To
avoid imbalance in the tree to search, apply operations that rearrange some
elements of the tree when adding or removing an item from it. These operations
are called Rotations. The type of rotation should be further specified and
depends on the implementation of the specific data structure. As examples for
structures like these we can give Red-Black
tree, AVL-tree, AA-tree, Splay-tree and others.
Non-binary balanced trees:
Non-binary
balanced search trees also have multiple implementations with different
special properties. Examples are B-
Trees, B+ Trees and Interval
Trees. All of them are ordered, balanced, but not binary. Their nodes can
typically hold more than one key and can have more than two child nodes. These
trees also perform operations like insert / search / delete very fast.
Perfect binary tree:
In this tree, Every node has exactly two
nodes and all levels are completely filled.
( or )
A perfect binary
tree is a binary tree in which all leaves have the same depth or
same level.
·
In general A perfect binary tree
satisfies all the properties of complete
and full binary trees.
·
For an Orderded perfect binary tree,
time complexity for search, insert and remove operations has O(logn).
Adblock is enabled