ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಡಿಬಿಒಐ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಇನ್ಫೋಸಿಸ್ MAQ ಒರಾಕಲ್
ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆ ಥಿಯರಿ ಮರ

ಈ ಲೇಖನದಲ್ಲಿ, ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಯ ಬಗ್ಗೆ ನಾವು ಓದುತ್ತೇವೆ. ಮರಗಳು ಕ್ರಮಾನುಗತ ದತ್ತಾಂಶ ರಚನೆಗಳಾಗಿವೆ, ಅಲ್ಲಿ ಪ್ರತಿ ನೋಡ್ ಮೂಲ ನೋಡ್ ಹೊರತುಪಡಿಸಿ ಮೂಲ ನೋಡ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಮಕ್ಕಳಿಲ್ಲದ ನೋಡ್‌ಗಳನ್ನು ಎಲೆಗಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಮರಗಳ ಅಗತ್ಯವಿದೆಯೇ?

1. ನಾವು ಕೆಲವು ಕ್ರಮಾನುಗತ ರೂಪದಲ್ಲಿ ಡೇಟಾವನ್ನು ಸಂಗ್ರಹಿಸಬೇಕಾದಾಗ ಮರಗಳನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆ: - ಫೈಲ್ ಸಿಸ್ಟಮ್ಸ್.

2. ಬಿಎಸ್ಟಿ ಯಂತಹ ಮರಗಳು ಒ (ಲಾಗ್ಎನ್) ಸಂಕೀರ್ಣತೆಯಲ್ಲಿ ಪ್ರವೇಶವನ್ನು ಒದಗಿಸುತ್ತವೆ, ಅದು ಲಿಂಕ್ಡ್ - ಲಿಸ್ಟ್ ಗಿಂತ ವೇಗವಾಗಿರುತ್ತದೆ.

3. ಮರಗಳಿಗೆ ಯಾವುದೇ ವ್ಯಾಖ್ಯಾನಿಸಲಾದ ಗಾತ್ರವಿಲ್ಲ ಮತ್ತು ಯಾವುದೇ ಸಂಖ್ಯೆಯ ನೋಡ್‌ಗಳನ್ನು ಮರದ ದತ್ತಾಂಶ ರಚನೆಗೆ ಸೇರಿಸಬಹುದು.

ಬೈನರಿ ಮರ

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಯು ಶ್ರೇಣೀಕೃತ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ. ಗರಿಷ್ಠ ಎರಡು ಮಕ್ಕಳೊಂದಿಗೆ ಇರುವ ಮರವನ್ನು ಬೈನರಿ ಟ್ರೀ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. Tts ಇಬ್ಬರು ಮಕ್ಕಳನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಎಡ ಮತ್ತು ಬಲ ಮಕ್ಕಳು ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

ಬೈನರಿ ಮರವು ಮೂರು ಘಟಕಗಳನ್ನು ಒಳಗೊಂಡಿದೆ:

  1. ನೋಡ್ನ ಮೌಲ್ಯ
  2. ಎಡ ಸಬ್‌ಟ್ರೀಗೆ ಸೂಚಿಸುವ ಪಾಯಿಂಟರ್
  3. ಬಲ ಸಬ್‌ಟ್ರೀಗೆ ಸೂಚಿಸುವ ಪಾಯಿಂಟರ್

 

ಎಡ ಮಗುವಿಗೆ ಪಾಯಿಂಟರ್ಮೌಲ್ಯ ಸರಿಯಾದ ಮಗುವಿಗೆ ಪಾಯಿಂಟರ್

ಮೂಲವನ್ನು ಸೂಚಿಸುತ್ತಿದ್ದರೆ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು ಅದು ಖಾಲಿ ಮರ.

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಗಾಗಿ ನೋಡ್

struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};

 

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆ

ಬೈನರಿ ಮರದಲ್ಲಿ ಬಳಸುವ ಪರಿಭಾಷೆಗಳು

  • ಬೇರು: It ಎಂಬುದು ಮರದ ಮೂಲ ನೋಡ್‌ಗೆ ಸೂಚಿಸಲು ನೋಡ್ ಪಾಯಿಂಟರ್ ವೇರಿಯೇಬಲ್ ಆಗಿದೆ. ಮೂಲವು ಶೂನ್ಯವನ್ನು ಹೊಂದಿರುವಾಗ, ಮರವು ಖಾಲಿಯಾಗಿರುತ್ತದೆ.
  • ಎಲೆ: ಶೂನ್ಯ ಡಿಗ್ರಿಗಳನ್ನು ಹೊಂದಿರುವ ನೋಡ್. ಇದನ್ನು ಬಾಹ್ಯ ನೋಡ್ ಎಂದೂ ಕರೆಯುತ್ತಾರೆ.
  • ಆಂತರಿಕ ನೋಡ್: ಕನಿಷ್ಠ ಒಂದು ಮಗುವಿನೊಂದಿಗೆ ನೋಡ್ ಮಾಡಿ.
  • ಪದವಿ: ನೋಡ್ನ ಒಟ್ಟು ಮಕ್ಕಳ ಸಂಖ್ಯೆಯನ್ನು ಅದರ ಪದವಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.
  • ಮರದ ಪದವಿ: ಮರದ ಪದವಿ ಎಲ್ಲಾ ನೋಡ್‌ಗಳ ಗರಿಷ್ಠ ಪದವಿ.
  • ಹಂತ: ಇದು ಮೂಲದಿಂದ ಕೊಟ್ಟಿರುವ ನೋಡ್ -1 ರವರೆಗಿನ ಒಟ್ಟು ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ.
  • ನೋಡ್ನ ಎತ್ತರ: ಇದು ಮೂಲದಿಂದ ನಿರ್ದಿಷ್ಟ ನೋಡ್‌ಗೆ ಒಟ್ಟು ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ

ಇಲ್ಲಿ ಮರದ ನೋಡ್‌ನಲ್ಲಿರುವ ಪೂರ್ಣಾಂಕ ಮೌಲ್ಯವನ್ನು ಯಾವುದೇ ಡೇಟಾಟೈಪ್ ಎಕ್ಸ್‌ನಿಂದ ಬದಲಾಯಿಸಬಹುದು. ಸ್ಟ್ರಿಂಗ್, ಚಾರ್, ಅರೇ, ಇತ್ಯಾದಿ. ಮರದಂತೆ ಕಾಣುತ್ತದೆ

TREE 
              1 <-- root node 
             / \ 
            2   3 <-- leaf node 
          / 
         4 <- leaf node

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಗಾಗಿ ಸಿ ++ ಕೋಡ್

//C++ Code


#include<bits/stdc++.h>
using namespace std ;


struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};


/* CreateNode() creates a new node with the given data with NULL left and right pointers. */


TreeNode* CreateNode(int data)
{
// Allocate memory for new node
TreeNode* NewNode = new TreeNode ;


// Assign data to this node
NewNode->data = data;


// Initialize left and right children as NULL
NewNode->left = NULL;
NewNode->right = NULL;


return(NewNode);


}




int main()
{
/*create root with data value 1*/
struct TreeNode *root = CreateNode(1);


/* following is the tree after above statement


                    1
                  /   \
               NULL   NULL
*/


root->left = CreateNode(2);
root->right = CreateNode(3);




/* 2 and 3 become left and right children of 1
                             1
                          /     \
                        2         3
                    /      \    /    \
                  NULL    NULL NULL   NULL
*/




root->left->left = CreateNode(4);




/* 4 becomes left child of 2
                                      1
                                  /       \
                                 2          3
                              /    \     /     \
                             4   NULL   NULL   NULL
                           /   \
                        NULL   NULL
*/
return 0 ;
}

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಗಾಗಿ ಜಾವಾ ಕೋಡ್

/* Class containing left and right child of current 
node and key value*/
class Node 
{ 
	int key; 
	Node left, right; 

	public Node(int item) 
	{ 
		key = item; 
		left = right = null; 
	} 
} 

// A Java program to introduce Binary Tree 
class BinaryTree 
{ 
	// Root of Binary Tree 
	Node root; 

	// Constructors 
	BinaryTree(int key) 
	{ 
		root = new Node(key); 
	} 

	BinaryTree() 
	{ 
		root = null; 
	} 

	public static void main(String[] args) 
	{ 
		BinaryTree tree = new BinaryTree(); 

		/*create root*/
		tree.root = new Node(1); 

		/* following is the tree after above statement 

			1 
			/ \ 
		null null	 */

		tree.root.left = new Node(2); 
		tree.root.right = new Node(3); 

		/* 2 and 3 become left and right children of 1 
			1 
			/ \ 
			2	 3 
		/ \ / \ 
		null null null null */


		tree.root.left.left = new Node(4); 
		/* 4 becomes left child of 2 
					1 
				/	 \ 
			2		 3 
			/ \	 / \ 
			4 null null null 
		/ \ 
		null null 
		*/
	} 
} 

ಬೈನರಿ ಟ್ರೀ ಡೇಟಾ ರಚನೆಯ ಗುಣಲಕ್ಷಣಗಳು

  1. H = H + 1 ಎತ್ತರದ ಬೈನರಿ ಮರದಲ್ಲಿನ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ನೋಡ್‌ಗಳು.
  2. H = 2 ಎತ್ತರದ ಬೈನರಿ ಮರದಲ್ಲಿ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ನೋಡ್‌ಗಳುಎಚ್ + 1 - 1
  3. ಬೈನರಿ ಮರದಲ್ಲಿನ ಎಲೆ ನೋಡ್‌ಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ = 2 ಮಕ್ಕಳೊಂದಿಗೆ ಒಟ್ಟು ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ + 1
  4. ಬೈನರಿ ಟ್ರೀ = 2 ನಲ್ಲಿ ಯಾವುದೇ ಮಟ್ಟದಲ್ಲಿ 'ಎಲ್' ನಲ್ಲಿ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ನೋಡ್‌ಗಳುL

SUMMARY

1. ಬೈನರಿ ಟ್ರೀ ಒಂದು ನೋಡ್ಗೆ ಗರಿಷ್ಠ ಎರಡು ಮಕ್ಕಳನ್ನು ಹೊಂದಿರುವ ಮರವಾಗಿದೆ.

2. ಮಕ್ಕಳಿಲ್ಲದ ನೋಡ್ ಅನ್ನು ಎಲೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಸ್ಟಾರ್ಟ್ ನೋಡ್ ಅನ್ನು ರೂಟ್ ನೋಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ.

3. ಒಂದು ಮರವು ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಒದಗಿಸುತ್ತದೆ: ಪ್ರವೇಶ, ಅಳವಡಿಕೆ, ರಚನೆಯಲ್ಲಿ ಅಳಿಸುವುದಕ್ಕಿಂತ ವೇಗವಾಗಿ ಅಳಿಸುವುದು.

ಉಲ್ಲೇಖಗಳು