Don't miss
Showing posts with label Tree. Show all posts
Showing posts with label Tree. Show all posts

## What is B Tree?

Most of us are confused with B tree and binary tree but they are much differ to each other.B tree(definition) is the balanced tree or we can say that it's a multi-way balanced tree and binary tree are those tree who's node have 0,1,2 children(s).It is used in c++,java,c# etc.

B tree satisfies following conditions:-

1)All leaf node have same level.
2)All non leaf node have n-1 keys.
3)All leaf node have m-1 keys.

Example of B-Tree(Animation and Algorithm):-

Suppose Order =5

than max. key value:-m-1
min. key value:-m-1/2.

13,3,16,5,180,4,6,2,10,24.

Step 1:-

Step 2:-

Step 3:-

Step 4:-

Step 5:-

Step 6:-

Step 7:-

Step 8:-

Step 9:-

Step 10:-

Step 11:-

## AVL Tree:Data Structure

AVL Tree is a tree which is widely used in data structures of C++,java,c# etc.AVL stands for Adelson-Velskki & Landis(Name of 2 Developers).Its a balanced binary tree.In this tree,the height between the right and left sub-tree never be more than 1.

Time Complexity of AVL tree in Big O notation:-

Operation    Average Case Complexity
Searching    O(log n)
Insertion    O(log n)
Deletion    O(log n)

AVL Tree Example(Algorithm & Animation):Right and Left Rotation:-

Example:-19,29,39,49,59,56,55,54,51.

Step 1:-

Step 2:-

Step 3:-

Step 4:-

Step 5:-

Step 6:-

Step 7:-

Step 8:-

## Tree Traversal(Binary Tree)

Tree Traversal or Traversing a binary tree is a method that refers as "to visit each node of tree in a specified order(exactly one times per node)".

Ways to traverse the tree:-

1)In-order Traversal:-

Procedure:-1)Traverse the left sub-tree.

2)Visits Root node.
3)Post Order traversal.

In simple words....Left-->Root-->Right or L(e)-->R-->R(i)

2)Post Order Traversal:-

Procedure:-1)Traverse Right Sub Tree.

2)Traverse Left Sub Tree.
3)Visits Root node.

In simple words....Right-->Left-->Root R(i)-->L(e)-->R

3)Preorder Traversal:-

Procedure:-1)Visits Root node.

2)Traverse Left Sub Tree.
3)Traverse Right Sub Tree.

In simple words....Root-->Left-->Right or R-->L(e)-->R(i)

Let us take an examples:-

Example 1:-

In Order:-E,B,D,G,K,J,I,H,F,A,C,N,M.

Post order:-E,K,J,I,H,G,F,D,B,N,M,C,A.

Preorder:-A,B,E,D,F,G,H,I,J,K,C,M,N.

Example 2:-

In Order:-K,G,L,H,M,D,B,A,E,O,Q,R,S,T,P,N,C.

Post Order:-K,L,M,H,G,D,B,T,S,R,Q,P,O,N,E,C,A.

Preorder:-A,B,D,G,K,L,H,M,C,E,N,O,P,Q,R,S,T.

Example 3:-(a*b)+(c/d)-e+(f^g)

In order:-a*b+c/d-e+f^g.

Post Order:-ab*cd/+efg^+-.

Preorder:--+*ab/cd+e^fg.

Example:- 4:-a*(b+c)-d/e+(f%g)^h.

In Order:-a*b+c-d/e+f%g^h.

Post Order:-abc+*de/-fg%h^+.

Preorder:-+-*a+bc/de^%fgh.

## What is Binary Tree?

Binary Tree in data structure are defined as those tree who's node have 0,1,2 children(s).As we know that general trees are made up of node,root etc.So binary tree also contains root,node,left pointer and the right pointer.In binary tree,tree consist node are called as root node,left and right node are called as Sub-tree.In this tree the degree of each  node is less than 2(<2).This tree deals in C ++,Java code etc.

Types of binary tree:-

1)Complete binary Tree:-Complete binary tree are those tree whose degree of every node is 2 or o.

No. of leaf node=2^level nodes.

Example:-

2)Almost complete Binary Tree:-In complete binary tree all the leaf are at the same level but in this type of binary tree all the leaf are in the bottom level.

3)Strictly binary tree:-Strictly binary tree are those tree whose degree of every node is 0 or 2.

Total no. of node=(2n-1).
where n=no. of leaf node.

## Tree(Computer Science) in data structure

Tree is an non-linear data structure which represent the hierarchical relationship between data items(nodes).Tree specified One:Many(1:M) relationship 1:M means one parent and more than one children but the child have the single parent.Tree deals in C++,java etc.

In the above example we tried to explain that what is root of tree,branch of tree,ancestor of tree,
descendant of tree,siblings of tree,degree of node,height of tree,depth of tree,generation of tree.
So starting with root of tree.

Root of tree:-Like the biological tree,computer tree has also contains root.

The node which are in the
beginning of tree called as root node.

Branch of Tree:-The line which connect nodes are called as branches of tree.

Leaf Node:-Leaf node are those node which have no children.This node also called as terminal node.

Non-Terminal Nodes:-Those node which possess children are called as terminal node.

Descendant of Tree:-Descendant is the path from node to leaf  node.For example the descendant of A to M are B and J.

Ancestor:-Ancestor is the path from node to root.For example ancestor of M are J,B,A.

Siblings of Tree:-The children node of the same parent are called as Siblings.

Generation of Tree:-Those node which are at same level are called as generation.

Degree of Node:-The sub-tree(s) of the node are called as Degree of node.For example degree of J is 3.

Note:-The node of degree 0 are called as leaf node.

Height/Depth of Tree:-The length of longest path from root to node is called as height of node.