### Day 22: Tree Data Structure

Hello Dear Students,

4. B+ Tree

Hope you all are doing good....

Aaj hum Tree data structure ko understand karenge with its types.

Let's get started...

**- Tree data structure is non linear data structure means isme jo data elements hote hain wo sequential nahi hote but it is hierarchical. Tree data structure is like tree means tree-like structure mein hota hai, at top parent node and then its child node. Tree is collection of various nodes and edges, isme nodes hoti hain jisme data elements ko store kiya jata hai and then edges se connect kiya jata hai nodes ko.**

__TREE DATA STRUCTURE__**-**

__Basic Tree Terminologies__**NODE**- Nodes mein data elements ko store kiya jata hai. It can be parent node, child node. For example, in above tree, nodes are A,B,C,D,E,and F.

**ROOT**- Root is topmost node of tree. IN above tree, root is A.

**EDGE**- Edge basically connecting lines hoti hain jo ek node ko doosri node ke saath connect karti hain. In above tree, AB mein jo line unko connect kar rahi hai wo edge hai, and so on.

**PARENT**- Parent node wo node hoti hai jiske child node hote hain. Root ki koi bhi parent node nahi hoti, Root khud parent node hai. In above tree,

A is parent of B and C

B is parent of D and E

C is parent of F.

**CHILD**- Child node wo node hoti hai jiski parent node ho. This is immediate successor of node. In above tree,

A has 2 child nodes, B and C.

B has 2 child nodes, D and E.

C has 1 child node, F.

**SIBLING**- Siblings means jo nodes same level par hon, means wo nodes jiske same parent node hon. In above tree,

B and C are siblings

D and E are siblings.

D, E and F bhi same level par hain but ye siblings nahi hain because parent same nahi hai. So, simply, jis node ke parent same hon wohi nodes siblings hoti hain.

**LEAF**- Leaf wo node hoti hai jiska koi bhi child node nahi hota and terminal nodes hoti hain wo. In above tree,

D, E, and F are leaf because ye terminal nodes hain jiske koi bhi child node nahi hai.

**PATH**- Nodes ko connect karne ke liye edges hote hain. So, ek node se doosri node tak jaane ke liye edges se jana hota hai, so wo uska path hota hai, In above tree, agar A to E jana hai so path will be- {A,B,E}.

**LEVEL**- Har ek node ka level hota hai. Root node level 0 se start hoti hai, then uski child nodes level 1 and then level 2 and so on. Root node se last node tak ke distance ko level kehte hain. In above tree, root node A is on level 0. B and C are on level 1 and D,E, and F are on level 2.

**DEPTH OF NODE**- Depth of node means har ek node ka level. In above tree,

Depth of node A is 0

Depth of node B, C is 1,

Depth of node D,E,F are 2.

**DEPTH OF TREE**- Means jo maximum level hai nodes ka. In above tree, maximum level is 2. So, simply depth of tree is 2.

**DEGREE OF NODE**- Degree of node means total number of its child node. Ek node ke jitne child nodes honge wo uski degree hoga. In above tree,

Degree of node A is 2

Degree of node B is 2

Degree of node C is 1

Degree of node D, E and F is 0

**DEGREE OF TREE**- Degree of tree means maximum degree of node jitni hai. Degree of tree find karne ke liye sabse pehle degree of node find karenge. So, from above, maximum degree of node is 2. So, degree of tree is 2 simply.

Ye terms exam ke point of view se important hain, so should be considered well.

**- Tree is of various types in data structure which are as follows-**

__TREE TYPES__- Forest
- Binary Tree

- Expression Tree
- Binary Search Tree
- Complete Binary Tree
- Threaded Binary Tree
- Heap
- AVL Tree

4. B+ Tree

**1. FOREST**- Simple term mein bhi forest is jisme bahut saare trees hote hain. So, tree data structure mein forest ka same hi meaning hai. Forest means collection or combination of tree data structures. Isme mostly 2 nodes ek edge ke saath hi connected hoti hain.

**2. BINARY TREE**- Binary tree wo tree hota hai jisme each parent node has maximum 2 child nodes only. Parent node ka 1 child node bhi ho sakta hai but 3 ya usse zyada nahi ho sakte only 0,1 or 2 child nodes hi ho sakte hain. Binary tree mein left and right child bhi ho sakte hain means jo left mein hai wo left child and jo right mein hai wo right child.

This is also a binary tree in which each parent node can have maximum 2 nodes only. C node mein 1 child node hai F, jo right child node hai. Binary tree is of various type as above.

**- Expression tree wo hota hai jo ki binary tree ho and jiske nodes mein basically arithmetic expressions hote hain. Arithmetic expressions can be-**

__EXPRESSION TREE__Binary Operators(+,-,/,*,%), Unary Operators(++,--,-ve).

In above, this is expression tree where +,*,/ are operators and D,E,F are operands.

**- Binary search tree wo hota hai jo ki binary tree ho and jo root node se left nodes hain wo sabhi root node se small hone chahiye and jo root node ke right nodes hain wo sabhi root node se large hone chahiye.**

__BINARY SEARCH TREE__**- Complete binary tree wo hota hai jo binary tree hota hai and uske sabhi parent nodes mein 2 child nodes hon but except leaf. Means sabhi parent nodes ke 2 child nodes hone chahiye but leaf nodes agar 1 bhi ho to bhi complete binary tree hoga. For example, in above tree, it is a complete binary tree, root node ke 2 child nodes hain and then 95 leaf node hai so wo 1 child bhi hai fir bhi complete binary tree hi hai.**

__COMPLETE BINARY TREE__**- Threaded binary tree wo hota hai jo binary tree hota hai and null values ko pointer se upper node ko point kiya jata hai. For example, in above tree, 90 has right child i.e. 95, but not have left child, so it is null. So, is null ko remove karne ke liye, pointers ko consider kiya jata hai jo ki upper node ki tarah point kare. Ye basically traversal mein use hota hai.**

__THREADED BINARY TREE__**- Heap is a complete binary tree. Heap is of 2 types, Max heap and Min Heap**

__HEAP__**Max Heap**- Max heap tree wo hota hai jisme har ek parent node ki value root node se zyada hoti hai. Isme right node left node ki values jo bhi hon but parent node child node se large honi chahiye.

Above is a max heap tree in which all child node value is small or equal to the parent node, but child node value is not large from parent node.

**Min Heap**- Min heap tree wo hota hai jisme har ek parent node ki value root node se small hoti hai.

Above is min heap in which all child node value is larger or equal to the parent node.

**- AVL Tree was developed by Adelson, Velskii, and Landis. So, AVL tree ka name uske developers ke name ke 1st letters se aya hai. It is also known as Height-Balanced Binary Tree. AVL Tree mein left nodes and right nodes dono ke difference and balance ko consider kiya jata hai.**

__AVL TREE__

*BF=H*_{L}-H_{R}Here, BF= Balance Factor, HL is height of left node, HR is height of right node.

AVL Tree mein dekha jata hai ki tree left heavy hai, right heavy hai, or balanced hai. If tree is left heavy then, balance factor is +ve and if tree is right heavy then balance factor is -ve. Height mein uske levels ko dekhna hai ki node kitne levels tak hai.

For example, in above tree, it is balanced tree, because simply levels same hain. If 80, 95 or 90 have child node, then it will be left heavy(if 80 and 95 have child node) and is right heavy(if 90 has any child node).

**3. B TREE**- B- Tree binary tree nahi hota hai. B Tree mein 2 se zyada chilren nodes bhi ho sakte hain. Jaise har ek node mein 1 data element store kiya jata hai to us data element ko Key kaha jata hai. So, B-Tree mein multiple keys hoti hain, means jaise above tree mein only 1 data element hai aise hi B-Tree mein multiple data elements ek hi node mein ho sakte hain separated by commas.

**4. B+Tree**- B-Tree data pointers ko store karta hai keys mein, and B+ Tree data pointers ko only leaf node mein store karta hai. So, it is better than B-Tree, and also have 2 or more childer nodes and have multiple keys as in B-Tree.

Best of Luck Students,

Do share and subscribe if you like our efforts..

Do visit our website regularly for more content and daily tests.

Regards,

**UGC NET EXPERTS**