أفضل طريقة لحساب الارتفاع في شجرة البحث الثنائية؟ (موازنة شجرة AVL)

Question

أبحث عن أفضل طريقة لحساب رصيد العقد في شجرة AVL. وبعد اعتقدت أنني كنت أعمل، ولكن بعد بعض الإدراج / التحديث الثقيل، يمكنني أن أرى أنه لا يعمل صحيح (على الإطلاق).

هذا هو نوع من سؤال جزءين، الجزء الأول سيكون كيفية حساب ارتفاع شجرة فرعية، وأنا أعلم التعريف "ارتفاع العقدة هو طول أطول طريق هبوطي إلى ورقة من تلك العقدة". وأنا أفهم ذلك، لكني فشلت في تنفيذها. والخلط بيني، يمكن العثور على هذا الاقتباس على ويكيبيديا على مرتفعات الأشجار "تقليديا، تتوافق القيمة -1 مع مجموعة كبيرة من عدم وجود عقد، في حين يتوافق الصفر مع مجموعة من العقدة مع عقدة واحدة."

والجزء الثاني هو الحصول على عامل التوازن لشجرة فرعية في شجرة AVL، ولدي مشكلة فهم المفهوم، "الحصول على ارتفاع الخاص بك L و R الأشجار الفرعية وطرح R من L". وبعد وهذا يعرف بأنه شيء مثل هذا: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

تقول القراءة على ويكيبيديا هذا في الأسطر القليلة الأولى التي تصف الإدراج في شجرة AVL: "إذا أصبح عامل التوازن -1، 0، أو 1، فإن الشجرة لا تزال في شكل AVL، ولا توجد تناوب ضرورية".

ثم يستمر، قائلا هذا "إذا أصبح عامل التوازن هو 2 أو -2، فإن الشجرة الجذور في هذه العقدة غير متوازنة، وهناك حاجة إلى دوران الأشجار. بالتناوب الوحيد أو المزدوج ستكون هناك حاجة إلى تحقيق التوازن بين الشجرة." - أي ليس لدي مشكلة في الاستيقاظ.

ولكن (نعم، هناك دائما ولكن).

إليك أين يحصل على مربكة، ينص النص "إذا كان عامل التوازن في R 1، فهذا يعني أنه حدث الإدراج على الجانب الأيمن (الخارجي) من تلك العقدة والتناوب الأيسر". وبعد ولكن من م فهم النص قال (كما نقلت) أنه إذا كان عامل التوازن في الداخل [-1, 1] ثم لم تكن هناك حاجة لتحقيق التوازن؟

أشعر أنني قريب جدا من استيعاب المفهوم، لقد حصلت على دورات الأشجار، ونفذت شجرة بحث ثنائية عادية، وعلى شفا أفلت أشجار AVL ولكن فقط يبدو أنها تفتقد أن ePiphany الأساسية.

يحرر: تفضل أمثلة التعليمات البرمجية على الصيغ الأكاديمية كما كان لدي دائما وقتا أسهل في استيعاب شيء ما في التعليمات البرمجية، لكن أي مساعدة موضع تقدير كبير.

يحرر: أتمنى أن أتمكن من وضع علامة على جميع الإجابات على أنها "مقبولة"، لكن بالنسبة لي كانت إجابة نيك هي الأولى التي جعلني أذهب "آها".

Answer 1

الجزء 1 - الارتفاع

كما يقول Starblue، الارتفاع يتكرر فقط. في كود الزائفة:

height(node) = max(height(node.L), height(node.R)) + 1

الآن يمكن تعريف الارتفاع بطريقتين. قد يكون عدد العقد في المسار من الجذر إلى تلك العقدة، أو يمكن أن يكون عدد الروابط. بحسب ال الصفحة التي تمت الرجوع إليها, ، التعريف الأكثر شيوعا هو لعدد الروابط. في هذه الحالة سيكون رمز الزائفة الكاملة:

height(node): 
   if node == null:
        return -1
   else:
        return max(height(node.L), height(node.R)) + 1

إذا كنت ترغب في أن يكون عدد العقد، فإن الرمز سيكون:

height(node): 
   if node == null:
        return 0
   else:
        return max(height(node.L), height(node.R)) + 1

وفي كلتا الحالتين، يجب أن تعمل خوارزمية إعادة التوازن على ما أعتقد أن العمل نفسه.

ومع ذلك، ستكون شجرة الخاص بك أكثر كفاءة (o (ln (n))) إذا قمت بتخزين وتحديث معلومات الارتفاع في الشجرة، بدلا من حسابه في كل مرة. فيعلى))

الجزء 2 - موازنة

عندما تقول "إذا كان عامل التوازن في R 1"، فهو يتحدث عن عامل التوازن في الفرع المناسب، عندما يكون عامل التوازن في الأعلى هو 2. يخبرك بكيفية اختيار ما إذا كنت تريد القيام بتدوير واحد أو دوران مزدوج. في (بيثون مثل) كود Pseudo:

if balance factor(top) = 2: // right is imbalanced
     if balance factor(R) = 1: // 
          do a left rotation
     else if balance factor(R) = -1:
          do a double rotation
else: // must be -2, left is imbalanced
     if balance factor(L) = 1: // 
          do a left rotation
     else if balance factor(L) = -1:
          do a double rotation

آمل أن يكون هذا الأمر يبدو معقولا تماما

Answer 2

• يتم تنفيذه الطول بسهولة من قبل العودية، واستغرق الحد الأقصى لارتفاع السكتة الدماغية بالإضافة إلى واحد.

• يشير "عامل التوازن في ص" إلى الشجرة اليمنى للشجرة التي هي خارج التوازن، أفترض.

Answer 3

لا تحتاج لحساب أعماق الشجرة على الطاير.

يمكنك الحفاظ عليها وأنت تؤدي العمليات.

علاوة على ذلك، لا تضطر في الواقع إلى الحفاظ على مسار الأعماق؛ يمكنك ببساطة تتبع الفرق بين أعماق الأشجار اليسرى واليمينية.

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

مجرد تتبع عامل التوازن (الفرق بين السكتونيات السكرية اليسرى واليمنى) هل وجدنا أسهل من البرمجة بوف، إلا أن فرز عامل التوازن بعد الدوران هو بيتا ...

Answer 4

إليك طريقة بديلة للعثور على الارتفاع. أضف سمة إضافية إلى عقدة تسمى الارتفاع:

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
}

هتافات،

Answer 5

حسنا، يمكنك حساب ارتفاع شجرة مع وظيفة العودية التالية:

int height(struct tree *t) {
    if (t == NULL)
        return 0;
    else
        return max(height(t->left), height(t->right)) + 1;
}

مع تعريف مناسب لل max() و struct tree. وبعد يجب أن تأخذ الوقت الكافي لمعرفة لماذا يتوافق هذا مع التعريف بناء على طول المسار الذي اقتباسه. تستخدم هذه الوظيفة صفر كأطول من الشجرة الفارغة.

ومع ذلك، لشيء مثل شجرة AVL، لا أعتقد أنك تحسب في الواقع الارتفاع في كل مرة تحتاج إليها. بدلا من ذلك، يتم زيادة كل عقدة شجرة مع حقل إضافي يتذكر ارتفاع Subtree الجذور في تلك العقدة. يجب أن يتم الاحتفاظ بهذا الحقل مع تعديل الشجرة بواسطة الإدراج والحذف.

أظن أنه إذا قمت بحساب الارتفاع في كل مرة بدلا من التخزين المؤقت داخل الشجرة كما هو مقترح أعلاه، فإن شكل شجرة AVL سيكون صحيحا، لكنه لن يكون له أداء لوغاريتمي المتوقع.

Answer 6

فيما يلي المكان الذي يحصل فيه على مربكة ونص النص "إذا كان عامل التوازن في R 1، فهذا يعني أنه حدث الإدراج على الجانب الأيمن (الخارجي) من تلك العقدة والتناوب الأيسر مطلوبة". ولكن من م فهم النص قال (كما نقلت) أنه إذا كان عامل التوازن في حدود [-1، 1] ثم لم تكن هناك حاجة لتحقيق التوازن؟

R هو الطفل الأيمن من العقدة الحالية N.

إذا balance(N) = +2, ، ثم تحتاج إلى دوران من نوع ما. ولكن أي دوران للاستخدام؟ حسنا، هذا يعتمد على balance(R): إذا balance(R) = +1 ثم تحتاج إلى التناوب الأيسر N; ؛ لكن اذا balance(R) = -1 ثم سوف تحتاج إلى دوران مزدوج من نوع ما.

Answer 7

فيما يلي المكان الذي يحصل فيه على مربكة ونص النص "إذا كان عامل التوازن في R 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

الآن، الشيء الكبير الذي يجب أن تلاحظه هنا - هذا الدوران الأيسر لم يغير عمق الشجرة. نحن لسنا أكثر توازنا لفعل ذلك.

ولكن - وهنا السحر في AVL - إذا استندنا الطفل المناسب إلى اليمين أولا، ما لدينا هو هذا ...

 P
  \
   O
    \
     LC
      \
       RC

والآن إذا قمنا بتدوير س اليسار، ما نحصل عليه هو هذا ...

 P
  \
   LC
  /  \
 O    RC

سحر! لقد تمكنا من التخلص من مستوى الشجرة - لقد صنعنا توازن الشجرة.

يعني تحقيق التوازن بين الشجرة التخلص من العمق الزائد، وتعبئة المستويات العليا أكثر تماما - وهذا هو بالضبط ما فعلناه للتو.

هذه الأشياء كلها حول الدوران الفردية / المزدوجة هي ببساطة يجب أن يكون لديك المشجع الفرعي الخاص بك تبدو وكأنها؛

 P
  \
   O
    \
     LC
      \
       RC

قبل التدوير - وقد تضطر إلى القيام بالتناوب الصحيح للوصول إلى هذه الحالة. ولكن إذا كنت بالفعل في هذه الحالة، فأنت بحاجة فقط إلى القيام بالتناوب الأيسر.

Answer 8

يعطى BinaryTree<T, Comparator>::Node أ subtreeHeight عضو في البيانات، مهيأة إلى 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;
}

إذا قمت بإزالة العقدة، استخدم نسخة مختلفة من 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.

Answer 9

هذا الحل الذي يشبه BFS واضح جدا. ببساطة يقفز مستويات واحدة تلو الأخرى.

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