Height Balanced Tree in Hindi | हाइट बैलेंस्ड ट्री क्या है?


हाइट बैलेंस्ड ट्री क्या है? (Height Balanced Tree in Hindi)

हाइट बैलेंस्ड ट्री (Height Balanced Tree) एक बाइनरी ट्री (Binary Tree) है, जिसमें बाएं और दाएं सब-ट्री की ऊंचाई (Height) में अंतर 1 से अधिक नहीं होता। यह सुनिश्चित करता है कि ट्री हमेशा संतुलित (Balanced) रहे और संचालन (Operations) तेज़ी से किए जा सकें।

हाइट बैलेंस्ड ट्री के नियम (Rules of Height Balanced Tree)

  • ट्री की ऊंचाई न्यूनतम होनी चाहिए।
  • हर नोड के बाएं और दाएं सब-ट्री की ऊंचाई का अंतर 1 या उससे कम होना चाहिए।
  • सभी ऑपरेशंस जैसे इन्सर्शन (Insertion), डिलीशन (Deletion) और सर्च (Search) को लॉगेरिथमिक समय में पूरा किया जाना चाहिए।

हाइट बैलेंस्ड ट्री के प्रकार (Types of Height Balanced Tree)

प्रकार विवरण
AVL ट्री (AVL Tree) बाइनरी ट्री जिसमें हर नोड का बैलेंस फैक्टर -1, 0 या 1 होता है।
रेड-ब्लैक ट्री (Red-Black Tree) स्वयं-संतुलन (Self-Balancing) बाइनरी ट्री जिसमें प्रत्येक नोड को लाल या काला रंग दिया जाता है।
B-ट्री (B-Tree) मल्टी-वे सर्च ट्री जिसका उपयोग डेटाबेस और फाइल सिस्टम में किया जाता है।
Splay ट्री (Splay Tree) स्वयं-संगठित (Self-Organizing) बाइनरी ट्री जो हाल ही में एक्सेस किए गए नोड्स को रूट के करीब ले आता है।

हाइट बैलेंस्ड ट्री में बैलेंस फैक्टर (Balance Factor in Height Balanced Tree)

बैलेंस फैक्टर को निम्नलिखित सूत्र से गणना किया जाता है:

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

बैलेंस फैक्टर की संभावित मान:

  • -1: दायां सब-ट्री लंबा है।
  • 0: ट्री संतुलित है।
  • 1: बायां सब-ट्री लंबा है।
  • |Balance Factor| > 1: ट्री असंतुलित (Unbalanced) है और इसे संतुलित करने की आवश्यकता है।

हाइट बैलेंस्ड ट्री की प्रक्रिया (Operations in Height Balanced Tree)

1. प्रत्येक नोड का बैलेंस फैक्टर निर्धारित करें।
2. यदि बैलेंस फैक्टर |1| से अधिक है, तो रोटेशन लागू करें।
3. निम्नलिखित चार प्रकार की रोटेशन का उपयोग किया जाता है:
   a. Left Rotation (LL Rotation)
   b. Right Rotation (RR Rotation)
   c. Left-Right Rotation (LR Rotation)
   d. Right-Left Rotation (RL Rotation)
4. नए नोड के लिए पुनः बैलेंस फैक्टर की गणना करें।

हाइट बैलेंस्ड ट्री का छद्मकोड (Pseudocode of Height Balanced Tree)

function insert(node, key):
    if node is NULL:
        return new Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    else:
        node.right = insert(node.right, key)
    
    update balance factor and height
    
    if balance factor > 1 and key < node.left.key:
        return rightRotate(node)
    if balance factor < -1 and key > node.right.key:
        return leftRotate(node)
    if balance factor > 1 and key > node.left.key:
        node.left = leftRotate(node.left)
        return rightRotate(node)
    if balance factor < -1 and key < node.right.key:
        node.right = rightRotate(node.right)
        return leftRotate(node)

    return node

हाइट बैलेंस्ड ट्री का उदाहरण (Example of Height Balanced Tree)

माना कि हम निम्नलिखित संख्याओं को एक खाली AVL ट्री में डालते हैं:

  • Insertion Sequence: 10, 20, 30, 40, 50, 25

बैलेंस फैक्टर की गणना करने के बाद, LL रोटेशन और LR रोटेशन का उपयोग करके हमें संतुलित ट्री प्राप्त होता है।

हाइट बैलेंस्ड ट्री बनाम अनबैलेंस्ड ट्री (Balanced Tree vs Unbalanced Tree)

विशेषता हाइट बैलेंस्ड ट्री अनबैलेंस्ड ट्री
खोज समय (Search Time) O(log n) O(n) (Worst Case)
इन्सर्शन / डिलीशन (Insertion/Deletion) तेज़ (Fast) धीमा (Slow)
स्टोरेज (Storage) संगठित (Organized) अव्यवस्थित (Unorganized)

हाइट बैलेंस्ड ट्री के अनुप्रयोग (Applications of Height Balanced Tree)

  • डेटाबेस इंडेक्सिंग (Database Indexing) – B-ट्री का उपयोग।
  • सर्च इंजन ऑप्टिमाइज़ेशन (Search Engine Optimization) – AVL ट्री।
  • नेटवर्क रूटिंग टेबल (Network Routing Tables)।
  • ऑपरेटिंग सिस्टम में प्रोसेस शेड्यूलिंग (Process Scheduling)।

निष्कर्ष

हाइट बैलेंस्ड ट्री एक महत्वपूर्ण डेटा संरचना है, जिसका उपयोग तेज़ और कुशल सर्च, इन्सर्शन और डिलीशन ऑपरेशंस के लिए किया जाता है। इसका उपयोग विभिन्न क्षेत्रों जैसे कि डेटाबेस, नेटवर्किंग और ऑपरेटिंग सिस्टम में किया जाता है।

Related Post

Comments

Comments