Types of binary tree

Types of binary tree

Full Binary Tree

A binary tree is full if each node has 0 or 2 children. We can also say that a full binary tree is a binary tree in which all the nodes, except the leaves, have two children.

Here are examples of full binary trees.

Complete binary tree

A binary tree is complete if all the levels are completely filled, except maybe the last level and the last level has all the keys as left as possible.

Perfect binary tree

A binary tree is perfect if all the internal nodes have two children and all the leaves are on the same level.

A perfect binary tree of height h a \(2^h - 1\) node.

Balanced binary tree

A binary tree is balanced if its height is \(O(log n)\), where n is the number of nodes.

  •   AVL trees maintains the height in \(O(log n)\) while ensuring that the difference between the heights of the left and right subtrees is 1.
  •   The red-black trees maintain the height in \(O(log n)\) ensuring that the number of black nodes on each root-to-leaf path is the same and that there are no adjacent red nodes.

Binary balanced search trees are good from a performance point of view because they provide \(O(log n)\) time for searching, inserting and deleting.

Share this course with your friends :

This course is written by M. ESSADDOUKI Mostafa

Many people realize their hearts desires late in life. Continue learning, never stop striving and keep your curiosity sharp, and you will never become too old to appreciate life.

0 Comment(s)

To leave a comment you must have an account Sign up, or Sign in