Types of Trees in Data Structures

Types of Trees in Data Structures

There are different types of trees in data structures and each have their own purpose let us look at different types of trees in Data Structures

tree

Types Overview

  • Tree (n-ary)
  • Binary
    • Full
    • Complete
    • Perfect
    • Balanced
  • Ternary
  • Binary Search Tree
  • AVL
  • Red Black Tree
  •  
Types

Tree (n-ary)

  • This type of set is a superset of any type of tree
  • A tree with at least one node(root/parent)
  • Any node can have any number of child nodes thus any degree
  • The node with highest number of child nodes defines the order(degree) of the tree
    • Example: If max child nodes are 2 then a binary tree, if max child nodes are 10 then n-ary tree with degree 10
  • It can be Full, Complete, Perfect, Balanced anything really
Trees in Data Structures n ary

Ternary (3 degrees)

  • A tree with highest degree being 3
  • In other words where max number of child nodes for any given node can not exceed than 3
Trees in Data Structures Ternary

Binary (2 degrees)

  • A tree with the highest degree being 2
  • In other words where the max number of child nodes for any given node can not exceed than 2
Trees in Data Structures Ternary

Types of Binary Trees

The following are different types of binary trees that can exist – 

1. Full Binary Tree

  • A binary tree is said to be a Full binary tree if all nodes except the leaf nodes have either 0 or 2 children. In other words the degree of such tree can either be  0 or 2.
  • In the given image, we can see that,
    • nodes ‘a’, ‘b’, ‘e’ have two child nodes each.
    • nodes ‘c’, ‘d’ have 0 child nodes.
  • Hence the given example is a full binary tree, also called strict binary tree.

A full binary tree with N leaves contains 2N – 1 nodes

In a Full Binary Tree, number of leaf nodes is the number of internal nodes plus 1
       L = I + 1

full

2. Complete Binary Tree

  • A binary tree is said to be a Complete binary tree if all the levels are completely filled except possibly the last level; and the last level has all the keys towards left.
  • In the given image, we can see that all the levels are fully filled with two child nodes each except the last levels which are oriented towards as left as possible, i.e,
    • the nodes ‘a’, ‘b’, ‘c’, ‘d’ have two child nodes each.
    • and the leaf nodes ‘h’, ‘i’, ‘j’ are oriented towards the left. 
  • Hence,  the given example can be concluded as a complete binary tree.
complete

3. Perfect Binary Tree

  • A binary tree is said to be a Perfect binary tree if all the internal nodes have exactly 2 children, all leaf nodes are at the same level.
  • In the given image, we can see that each node in the tree except the leaf nodes have exactly two children, i.e, the nodes ‘a’, ‘b’, ‘c’ have exactly two children each.

A Perfect Binary Tree of height h has:

  • (2h+1 – 1)nodes  (if h starts from 0)
  • (2h – 1)nodes  (if h starts from 1)
perfect

4. Balanced Binary Tree

  • A binary tree is said to be a Balanced binary tree if, for each node it holds that the number of inner nodes in the left sub tree and the number of inner nodes in the right sub tree differ by at most 1.
  • In this image, we can see at different respective levels the difference in height between the left and the right sub trees. For instance,
    • at node ‘a’ the difference between the left sub tree ‘b’ and the right sub tree ‘c’ is 1.
    • at node ‘e’ the difference between the left sub tree ‘—‘  and the right sub tree ‘j’ is 1.
    • at node ‘d’ the difference between the left sub tree ‘h’ and the right sub tree ‘i’  is 0. 
  • From this we can conclude that the given image is an example of a balanced binary tree.
balanced

Other types of Trees

Binary Search Tree

A binary search tree is nothing but an advanced version of a binary tree.

  • All properties of binary tree exist, for example, max degree(order) is 2
  • Left child value should be less than or equal to any parent node’s value
  • Right child value should be larger than or equal to parents node’s value

This is very good for doing search and are many many applications for the same in the real world. As the search is very efficient and fast.

Binary Search Tree

AVL Tree

AVL was named after Adelson-Velshi and Landis. This is an example of a tree that is balanced dynamically.

  • AVL tree is a binary search tree self-balancing. 
  • We allocate a balancing factor for each node in the AVL tree, by checking if the tree is balanced or not
  • The height of the node kids is at most 1. AVL vine.
  • In the AVL tree, the correct balance factor is 1, 0 and -1.
  • When we want to enter a new node, then we will rotate the tree to make sure that the tree is always balanced. 
  • View, Insert and remove happen at O(log n)
  • Generally, we apply it when we are going operations like lookup, example searching in your phone’s contacts directory
AVL Search Tree (1)

Red Black Tree

  • This another example of a tree that is auto-balancing
  • The name is given because either a node will be painted as red or black, according to red-black tree properties
  • A red-black tree should always the balance of the forest.
  • Even though this tree is not a fully balanced tree, the searching operation only takes O (log n) time.
  • When adding a new node, we should always rotate the tree to make sure that the tree’s properties are always maintained.
Red Black Tree