wake-up-neo.com

Der beste Weg, um die Höhe in einem binären Suchbaum zu berechnen? (Ausgleich eines AVL-Baums)

Ich suche nach dem besten Weg, um ein Knotengleichgewicht in einem AVL-Baum zu berechnen. Ich dachte, ich hätte es funktioniert, aber nach einigen schweren Einfügungen/Aktualisierungen kann ich sehen, dass es (überhaupt) nicht richtig funktioniert.

Dies ist eine Art zweiteilige Frage, der erste Teil wäre, wie man die Höhe eines Teilbaums berechnet. Ich kenne die Definition "Die Höhe eines Knotens ist die Länge des längsten Abwärtspfades zu a Blatt von diesem Knoten. " und ich verstehe es, aber ich kann es nicht implementieren. Und um mich weiter zu verwirren, finden Sie dieses Zitat in Wikipedia auf Baumhöhen "Herkömmlicherweise entspricht der Wert -1 einem Teilbaum ohne Knoten, wohingegen Null einem Teilbaum mit einem Knoten entspricht." =

Und der zweite Teil ist das Ermitteln des Ausgleichsfaktors eines Unterbaums in einem AVL-Baum. Ich habe kein Problem damit, das Konzept zu verstehen. "Ermitteln Sie die Höhe Ihrer L und R Unterbäume und subtrahieren R von L ". Und das ist wie folgt definiert: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

In den ersten Zeilen, in denen Einfügungen in einen AVL-Baum beschrieben werden, heißt es in Wikipedia: "Wenn der Ausgleichsfaktor -1, 0 oder 1 wird, befindet sich der Baum noch in AVL-Form, und es sind keine Rotationen erforderlich."

Es geht dann weiter und sagt dies "Wenn der Ausgleichsfaktor 2 oder -2 wird, ist der Baum, der an diesem Knoten verwurzelt ist, unausgeglichen, und es ist eine Baumrotation erforderlich. Zum Ausgleich ist höchstens eine einfache oder doppelte Rotation erforderlich der Baum. " - was ich ohne Probleme erfassen kann.

Aber (ja, es gibt immer ein Aber).

Hier wird es verwirrend, der Text besagt "Wenn der Ausgleichsfaktor von R 1 ist, bedeutet dies, dass die Einfügung auf der (externen) rechten Seite dieses Knotens erfolgt ist und eine Linksrotation erforderlich ist" . Aber nach meinem Verständnis sagte der Text (wie ich zitiert habe), dass, wenn der Ausgleichsfaktor innerhalb von [-1, 1] war dann kein ausgleich nötig?

Ich habe das Gefühl, dass ich dem Konzept so nahe bin, dass ich die Baumrotation runtergefahren habe, einen normalen binären Suchbaum implementiert habe und kurz davor stehe, AVL-Bäume zu erfassen.

Bearbeiten: Codebeispiele werden gegenüber akademischen Formeln bevorzugt, da es mir immer leichter gefallen ist, etwas im Code zu erfassen, aber jede Hilfe wird sehr geschätzt.

Edit: Ich wünschte, ich könnte alle Antworten als "akzeptiert" markieren, aber für mich war Nicks Antwort die erste, die mich dazu brachte, "aha" zu machen.

60
thr

Teil 1 - Höhe

Wie Starblue sagt, ist die Höhe nur rekursiv. Im Pseudocode:

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

Jetzt kann die Höhe auf zwei Arten definiert werden. Dies kann die Anzahl der Knoten im Pfad vom Stamm zu diesem Knoten oder die Anzahl der Links sein. Laut Seite, auf die Sie verwiesen haben ist die gebräuchlichste Definition die Anzahl der Links. In diesem Fall wäre der vollständige Pseudocode:

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

Wenn Sie die Anzahl der Knoten haben möchten, wäre der Code:

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

In jedem Fall sollte der Algorithmus zur Neuverteilung meiner Meinung nach genauso funktionieren.

Ihr Baum ist jedoch viel effizienter ( O (ln (n)) ), wenn Sie Höheninformationen im Baum speichern und aktualisieren, anstatt zu berechnen es jedes Mal. ( O (n) )

Teil 2 - Auswuchten

Wenn "Wenn der Ausgleichsfaktor von R 1 ist" angezeigt wird, handelt es sich um den Ausgleichsfaktor des rechten Zweigs, wenn der Ausgleichsfaktor oben 2 ist. Hier erfahren Sie, wie Sie auswählen können, ob eine einzelne Drehung oder eine Drehung ausgeführt werden soll eine doppelte Drehung. Im (pythonartigen) Pseudocode:

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

Ich hoffe das macht Sinn

78
Nick Fortescue
  • Die Höhe wird einfach durch Rekursion implementiert. Nehmen Sie das Maximum der Höhe der Teilbäume plus eins.

  • Der "Gleichgewichtsfaktor von R" bezieht sich auf den rechten Teilbaum des Baumes, der aus dem Gleichgewicht geraten ist, nehme ich an.

4
starblue

Sie müssen die Baumtiefen nicht im laufenden Betrieb berechnen.

Sie können sie während der Ausführung von Vorgängen pflegen.

Darüber hinaus müssen Sie die Tiefen nicht unbedingt im Auge behalten. Sie können einfach den Unterschied zwischen der linken und der rechten Baumtiefe verfolgen.

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

Nur den Balance-Faktor (Unterschied zwischen linkem und rechtem Teilbaum) im Auge zu behalten, fällt mir bei einem Programmier-POV leichter, mit der Ausnahme, dass das Aussortieren des Balance-Faktors nach einer Rotation ein PITA ist ...

4
user82238

Hier ist eine alternative Methode, um die Höhe zu ermitteln. Fügen Sie Ihrem Knoten ein zusätzliches Attribut mit dem Namen height hinzu:

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

Jetzt führen wir eine einfache Durchquerung des Baums von der ersten Breite aus und aktualisieren den Höhenwert für jeden Knoten:

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
}

Prost,

2
L8Again

Nun, Sie können die Höhe eines Baumes mit der folgenden rekursiven Funktion berechnen:

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

mit einer entsprechenden Definition von max() und struct tree. Sie sollten sich die Zeit nehmen, um herauszufinden, warum dies der Definition auf der Grundlage der von Ihnen angegebenen Pfadlänge entspricht. Diese Funktion verwendet Null als Höhe des leeren Baums.

Für so etwas wie einen AVL-Baum glaube ich jedoch nicht, dass Sie die Höhe jedes Mal berechnen, wenn Sie sie benötigen. Stattdessen wird jeder Baumknoten um ein zusätzliches Feld erweitert, das die Höhe des untergeordneten Baums speichert, der auf diesem Knoten verwurzelt ist. Dieses Feld muss auf dem neuesten Stand gehalten werden, da der Baum durch Einfügungen und Löschungen geändert wird.

Ich vermute, dass, wenn Sie die Höhe jedes Mal berechnen, anstatt sie wie oben vorgeschlagen im Baum zwischenzuspeichern, die AVL-Baumform korrekt ist, aber nicht die erwartete logarithmische Leistung aufweist.

1
Dale Hagglund

Hier wird es verwirrend. Im Text heißt es: "Wenn der Ausgleichsfaktor von R 1 ist, bedeutet dies, dass die Einfügung auf der (externen) rechten Seite dieses Knotens erfolgt ist und eine Drehung nach links erforderlich ist." Aber nach meinem Verständnis sagte der Text (wie ich zitiert habe), dass, wenn der Ausgleichsfaktor innerhalb von [-1, 1] lag, es keine Notwendigkeit für einen Ausgleich gab?

R ist das rechte untergeordnete Element des aktuellen Knotens N.

Wenn balance(N) = +2, dann brauchen Sie eine Art Rotation. Aber welche Rotation soll man verwenden? Nun, es hängt von balance(R) ab: wenn balance(R) = +1, dann brauchen Sie eine Linksdrehung auf N; aber wenn balance(R) = -1, dann brauchen Sie eine Art Doppelrotation.

1
yfeldblum

Hier wird es verwirrend. Im Text heißt es: "Wenn der Ausgleichsfaktor von R 1 ist, bedeutet dies, dass die Einfügung auf der (externen) rechten Seite dieses Knotens erfolgt ist und eine Drehung nach links erforderlich ist." Aber nach meinem Verständnis sagte der Text (wie ich zitiert habe), dass, wenn der Ausgleichsfaktor innerhalb von [-1, 1] lag, es keine Notwendigkeit für einen Ausgleich gab?

Okay, Offenbarungszeit.

Überlegen Sie, was eine Drehung bewirkt. Denken wir über eine Linksdrehung nach.

 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

Nun, die große Sache, die Sie hier bemerken müssen - diese Linksdrehung HAT DIE TIEFE DES BAUMES NICHT GEÄNDERT. Wir sind nicht mehr ausgeglichen, dass wir es geschafft haben.

Aber - und hier ist die Magie in AVL - wenn wir das richtige Kind ZUERST nach rechts drehen würden, hätten wir Folgendes ...

 P
  \
   O
    \
     LC
      \
       RC

Und JETZT, wenn wir O nach links drehen, erhalten wir Folgendes ...

 P
  \
   LC
  /  \
 O    RC

Zauber! wir haben es geschafft, eine Ebene des Baumes loszuwerden - wir haben die Baumbalance hergestellt.

Wenn wir den Baum balancieren, müssen wir überschüssige Tiefe beseitigen und die oberen Ebenen vollständiger einpacken - genau das haben wir gerade getan.

Das ganze Zeug über einfache/doppelte Rotationen ist einfach, dass Sie Ihren Teilbaum so aussehen lassen müssen;

 P
  \
   O
    \
     LC
      \
       RC

bevor Sie drehen - und Sie müssen möglicherweise nach rechts drehen, um in diesen Zustand zu gelangen. Wenn Sie sich jedoch bereits in diesem Zustand befinden, müssen Sie nur die Drehung nach links ausführen.

1
user82238

Diese BFS-ähnliche Lösung ist ziemlich einfach. Springt einfach Levels eins nach dem anderen.

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
0
realmaniek

Geben Sie BinaryTree<T, Comparator>::Node Ein subtreeHeight -Datenelement, das in seinem Konstruktor auf 0 initialisiert wurde, und aktualisieren Sie es jedes Mal automatisch mit:

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;
    }
}

Beachten Sie, dass die Datenelemente subtreeSize und depthFromRoot ebenfalls aktualisiert werden. Diese Funktionen werden beim Einfügen eines Knotens (alle getestet) aufgerufen, z.

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;
}

Wenn Sie einen Knoten entfernen, verwenden Sie eine andere Version von removeLeft und removeRight, indem Sie subtreeSize++; Durch subtreeSize--; Ersetzen. Algorithmen für rotateLeft und rotateRight können ebenfalls problemlos angepasst werden. Folgendes wurde getestet und bestanden:

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; 
    }
}

woher

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);
}

Hier ist der gesamte Code: http://ideone.com/d6arrv

0
prestokeys