algorithm - एक बाइनरी खोज पेड़ में ऊंचाई की गणना करने का सबसे अच्छा तरीका है?(एक एवीएल-पेड़ को संतुलित करना)




data-structures binary-tree (6)

यहां बताया गया है कि यह भ्रमित हो जाता है, पाठ कहता है "यदि आर का शेष कारक 1 है, तो इसका मतलब है कि उस नोड के बाहरी (बाहरी) दाएं तरफ सम्मिलन हुआ और बाएं रोटेशन की आवश्यकता है"। लेकिन मुझे समझने से पाठ ने कहा (जैसा कि मैंने उद्धृत किया है) कि यदि संतुलन कारक [-1, 1] के भीतर था तो संतुलन की कोई आवश्यकता नहीं थी?

ठीक है, epiphany समय।

विचार करें कि एक घूर्णन क्या करता है। चलो बाएं रोटेशन के बारे में सोचें।

 P = parent
 O = ourself (the element we're rotating)
 RC = right child
 LC = left child (of the right child, not of ourself)

 P
  \
   O
    \
     RC
    /
   LC

  P
   \
    RC
   /
  O
   \
    LC

 10
   \
    15
      \
       20
      /
    18

 10
   \
    20
   /
 15
   \
    18 

 basically, what happens is;

 1. our right child moves into our position
 2. we become the left child of our right child
 3. our right child's left child becomes our right

अब, आपको यहां बड़ी सूचना देने की ज़रूरत है - यह बाएं रोटेशन ट्री के डेथ को बदल नहीं गया है। हम इसे करने के लिए और अधिक संतुलित नहीं हैं।

लेकिन - और यहां एवीएल में जादू है - अगर हमने सही बच्चे को दाहिने ओर घुमाया है, तो हमारे पास यह क्या होगा ...

 P
  \
   O
    \
     LC
      \
       RC

और अब अगर हम बाएं घुमाते हैं, तो हमें यह क्या मिलता है ...

 P
  \
   LC
  /  \
 O    RC

जादू! हम पेड़ के एक स्तर से छुटकारा पाने में कामयाब रहे हैं - हमने वृक्ष संतुलन बनाया है

पेड़ को संतुलित करना मतलब है कि अतिरिक्त गहराई से छुटकारा पाएं, और ऊपरी स्तरों को पूरी तरह से पैक करना - जो हमने अभी किया है।

सिंगल / डबल रोटेशन के बारे में वह सारी चीजें बस यह है कि आपको अपनी उपट्री इस तरह दिखाना है;

 P
  \
   O
    \
     LC
      \
       RC

घुमाने से पहले - और आपको उस स्थिति में जाने के लिए सही घुमावदार करना पड़ सकता है। लेकिन अगर आप पहले से ही उस राज्य में हैं, तो आपको केवल बाएं घुमाने की जरूरत है।

मैं AVL-tree में नोड्स बैलेंस की गणना करने का सबसे अच्छा तरीका ढूंढ रहा हूं। मैंने सोचा कि मैंने यह काम किया है, लेकिन कुछ भारी डालने / अपडेट करने के बाद मैं देख सकता हूं कि यह सही काम नहीं कर रहा है (बिल्कुल)।

यह एक दो भाग का सवाल है, पहला भाग उप-पेड़ की ऊंचाई की गणना कैसे करेगा, मुझे परिभाषा पता है "नोड की ऊंचाई उस नोड के पत्ते के सबसे लंबे समय तक नीचे की लंबाई की लंबाई है । " और मैं इसे समझता हूं, लेकिन मैं इसे लागू करने में विफल रहता हूं। और मुझे आगे भ्रमित करने के लिए यह उद्धरण पेड़-ऊंचाइयों पर विकिपीडिया पर पाया जा सकता है "परंपरागत रूप से, मान -1 किसी नोड्स के साथ एक उप-धारा से मेल खाता है, जबकि शून्य एक नोड के साथ एक उप-योग से मेल खाता है।"

और दूसरा भाग एवीएल पेड़ में एक उप-पेड़ का संतुलन कारक प्राप्त कर रहा है, मुझे अवधारणा को समझने में कोई समस्या नहीं है, "अपने L और R उप-पेड़ की ऊंचाई प्राप्त करें और L से R घटाएं" । और इसे इस तरह कुछ परिभाषित किया गया है: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

विकिपीडिया पर पढ़ना यह कुछ एवीएल पेड़ में सम्मिलन का वर्णन करने वाली पहली कुछ पंक्तियों पर कहता है: "यदि शेष कारक -1, 0, या 1 हो जाता है तो पेड़ अभी भी एवीएल रूप में है, और कोई रोटेशन आवश्यक नहीं है।"

इसके बाद यह कहता है, "यदि संतुलन कारक 2 या -2 हो जाता है तो इस नोड पर जड़ पेड़ असंतुलित होता है, और पेड़ के घूर्णन की आवश्यकता होती है। पेड़ को संतुलित करने के लिए अधिकतम या दोहरा घूर्णन की आवश्यकता होगी।" - जो मुझे परेशान करने में कोई परेशानी नहीं है।

लेकिन (हाँ, हमेशा एक है लेकिन)।

यहां बताया गया है कि यह भ्रमित हो जाता है, पाठ कहता है "यदि आर का शेष कारक 1 है, तो इसका मतलब है कि उस नोड के बाहरी (बाहरी) दाएं तरफ सम्मिलन हुआ और बाएं रोटेशन की आवश्यकता है" । लेकिन मुझे समझने से पाठ ने कहा (जैसा कि मैंने उद्धृत किया है) कि यदि संतुलन कारक [-1, 1] भीतर था तो संतुलन की कोई आवश्यकता नहीं थी?

मुझे लगता है कि मैं अवधारणा को समझने के बहुत करीब हूं, मैंने पेड़ के घूर्णन को नीचे कर लिया है, एक सामान्य द्विआधारी खोज वृक्ष लागू किया है, और एवीएल-पेड़ों को पकड़ने के कगार पर है, लेकिन ऐसा लगता है कि वह आवश्यक एपिफेनी गायब है।

संपादित करें: अकादमिक सूत्रों पर कोड उदाहरणों को प्राथमिकता दी जाती है क्योंकि मेरे पास हमेशा कोड में कुछ समझने में आसान समय होता है, लेकिन किसी भी मदद की बहुत सराहना की जाती है।

संपादित करें: काश मैं सभी उत्तरों को "स्वीकृत" के रूप में चिह्नित कर सकता हूं, लेकिन मेरे लिए एनआईक का जवाब पहला था जिसने मुझे "आह" बनाया।


यहां बताया गया है कि यह भ्रमित हो जाता है, पाठ कहता है "यदि आर का शेष कारक 1 है, तो इसका मतलब है कि उस नोड के बाहरी (बाहरी) दाएं तरफ सम्मिलन हुआ और बाएं रोटेशन की आवश्यकता है"। लेकिन मुझे समझने से पाठ ने कहा (जैसा कि मैंने उद्धृत किया है) कि यदि संतुलन कारक [-1, 1] के भीतर था तो संतुलन की कोई आवश्यकता नहीं थी?

R वर्तमान नोड N का दायां हाथ है।

यदि balance(N) = +2 , तो आपको किसी प्रकार के घूर्णन की आवश्यकता है। लेकिन किस घूर्णन का उपयोग करने के लिए? खैर, यह balance(R) पर निर्भर करता है: यदि balance(R) = +1 तो आपको N पर बाएं-रोटेशन की आवश्यकता होती है; लेकिन अगर balance(R) = -1 तो आपको किसी प्रकार के डबल-रोटेशन की आवश्यकता होगी।


आपको फ्लाई पर पेड़ की गहराई की गणना करने की आवश्यकता नहीं है।

जब आप संचालन करते हैं तो आप उन्हें बनाए रख सकते हैं।

इसके अलावा, वास्तव में आपको वास्तव में गहराइयों का ट्रैक बनाए रखना नहीं है; आप बस बाएं और दाएं पेड़ की गहराई के बीच के अंतर का ट्रैक रख सकते हैं।

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

बस संतुलन कारक (बाएं और दाएं उपट्री के बीच अंतर) का ट्रैक रखना मुझे प्रोग्रामिंग पीओवी से आसान पाया गया है, सिवाय इसके कि एक घूर्णन के बाद संतुलन कारक को सॉर्ट करना एक पिटा है ...


ऊंचाई खोजने का एक वैकल्पिक तरीका यहां दिया गया है। ऊंचाई नामक अपने नोड में एक अतिरिक्त विशेषता जोड़ें:

class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}

अब, हम पेड़ की एक साधारण चौड़ाई-पहले ट्रैवर्सल करेंगे, और प्रत्येक नोड के लिए ऊंचाई मान अपडेट करते रहेंगे:

int height (Node root)
{
Queue<Node> q = Queue<Node>();
Node lastnode;
//reset height
root.height = 0;

q.Enqueue(root);
while(q.Count > 0)
{
   lastnode = q.Dequeue();
   if (lastnode.left != null){
      lastnode.left.height = lastnode.height + 1; 
      q.Enqueue(lastnode.left);
   }

   if (lastnode.right != null){
      lastnode.right.height = lastnode.height + 1;
      q.Enqueue(lastnode.right);
   }
}
return lastnode.height; //this will return a 0-based height, so just a root has a height of 0
}

चीयर्स,


यह बीएफएस-जैसे समाधान बहुत सरल है। बस एक-एक करके स्तर कूदता है।

def getHeight(self,root, method='links'):
    c_node = root
    cur_lvl_nodes = [root]
    nxt_lvl_nodes = []
    height = {'links': -1, 'nodes': 0}[method]

    while(cur_lvl_nodes or nxt_lvl_nodes):
        for c_node in cur_lvl_nodes:
            for n_node in filter(lambda x: x is not None, [c_node.left, c_node.right]):
                nxt_lvl_nodes.append(n_node)

        cur_lvl_nodes = nxt_lvl_nodes
        nxt_lvl_nodes = []
        height += 1

    return height

subtreeHeight BinaryTree<T, Comparator>::Node subtreeHeight BinaryTree<T, Comparator>::Node एक subtreeHeight डेटा सदस्य BinaryTree<T, Comparator>::Node , इसके कन्स्ट्रक्टर में 0 तक प्रारंभ किया गया है, और हर बार स्वचालित रूप से अपडेट करें:

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setLeft (std::shared_ptr<Node>& node) {
    const std::size_t formerLeftSubtreeSize = left ? left->subtreeSize : 0;
    left = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (right)
            subtreeHeight = std::max (right->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerLeftSubtreeSize;
        subtreeHeight = right ? right->subtreeHeight + 1 : 0;
    }
}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::Node::setRight (std::shared_ptr<Node>& node) {
    const std::size_t formerRightSubtreeSize = right ? right->subtreeSize : 0;
    right = node;
    if (node) {
        node->parent = this->shared_from_this();
        subtreeSize++;
        node->depthFromRoot = depthFromRoot + 1;
        const std::size_t h = node->subtreeHeight;
        if (left)
            subtreeHeight = std::max (left->subtreeHeight, h) + 1;
        else
            subtreeHeight = h + 1;
    }
    else {
        subtreeSize -= formerRightSubtreeSize;
        subtreeHeight = left ? left->subtreeHeight + 1 : 0;
    }
}

ध्यान दें कि डेटा सदस्य subtreeSize और depthFromRoot भी अद्यतन कर रहे हैं। इन कार्यों को नोड (सभी परीक्षण) डालने पर बुलाया जाता है, उदाहरण के लिए

template <typename T, typename Comparator>
inline std::shared_ptr<typename BinaryTree<T, Comparator>::Node>
BinaryTree<T, Comparator>::Node::insert (BinaryTree& tree, const T& t, std::shared_ptr<Node>& node) {
    if (!node) {
        std::shared_ptr<Node> newNode = std::make_shared<Node>(tree, t);
        node = newNode;
        return newNode;
    }
    if (getComparator()(t, node->value)) {
        std::shared_ptr<Node> newLeft = insert(tree, t, node->left);
        node->setLeft(newLeft);
    }
    else {
        std::shared_ptr<Node> newRight = insert(tree, t, node->right);
        node->setRight(newRight);
    }
    return node;
}

यदि नोड को हटाते हैं, तो subtreeSize++; को प्रतिस्थापित करके removeLeft एक अलग संस्करण का removeLeft और removeRight subtreeSize++; subtreeSize--;rotateLeft और rotateRight लिए एल्गोरिदम या तो बहुत अधिक समस्या के बिना अनुकूलित किया जा सकता है। निम्नलिखित परीक्षण और पारित किया गया था:

template <typename T, typename Comparator>
void BinaryTree<T, Comparator>::rotateLeft (std::shared_ptr<Node>& node) {  // The root of the rotation is 'node', and its right child is the pivot of the rotation.  The pivot will rotate counter-clockwise and become the new parent of 'node'.
    std::shared_ptr<Node> pivot = node->right;
    pivot->subtreeSize = node->subtreeSize;
    pivot->depthFromRoot--;
    node->subtreeSize--;  // Since 'pivot' will no longer be in the subtree rooted at 'node'.
    const std::size_t a = pivot->left ? pivot->left->subtreeHeight + 1 : 0;  // Need to establish node->heightOfSubtree before pivot->heightOfSubtree is established, since pivot->heightOfSubtree depends on it.
    node->subtreeHeight = node->left ? std::max(a, node->left->subtreeHeight + 1) : std::max<std::size_t>(a,1);
    if (pivot->right) {
        node->subtreeSize -= pivot->right->subtreeSize;  // The subtree rooted at 'node' loses the subtree rooted at pivot->right.
        pivot->subtreeHeight = std::max (pivot->right->subtreeHeight, node->subtreeHeight) + 1;
    }
    else
        pivot->subtreeHeight = node->subtreeHeight + 1;
    node->depthFromRoot++;
    decreaseDepthFromRoot(pivot->right);  // Recursive call for the entire subtree rooted at pivot->right.
    increaseDepthFromRoot(node->left);  // Recursive call for the entire subtree rooted at node->left.
    pivot->parent = node->parent;
    if (pivot->parent) {  // pivot's new parent will be its former grandparent, which is not nullptr, so the grandparent must be updated with a new left or right child (depending on whether 'node' was its left or right child).
        if (pivot->parent->left == node)
            pivot->parent->left = pivot;
        else
            pivot->parent->right = pivot;
    }
    node->setRightSimple(pivot->left);  // Since pivot->left->value is less than pivot->value but greater than node->value.  We use the NoSizeAdjustment version because the 'subtreeSize' values of 'node' and 'pivot' are correct already.
    pivot->setLeftSimple(node);
    if (node == root) {
        root = pivot;
        root->parent = nullptr; 
    }
}

कहा पे

inline void decreaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, -1);}
inline void increaseDepthFromRoot (std::shared_ptr<Node>& node) {adjustDepthFromRoot(node, 1);}

template <typename T, typename Comparator>
inline void BinaryTree<T, Comparator>::adjustDepthFromRoot (std::shared_ptr<Node>& node, int adjustment) {
    if (!node)
        return;
    node->depthFromRoot += adjustment;
    adjustDepthFromRoot (node->left, adjustment);
    adjustDepthFromRoot (node->right, adjustment);
}

यहां पूरा कोड है: http://ideone.com/d6arrv





tree-balancing