Der beste Weg, um die Höhe in einem binären Suchbaum zu berechnen? (Ausgleich ein AVL-Baum)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin auf der Suche nach dem besten Weg, einen Knoten Balance in einem AVL-Baum zu berechnen . Ich dachte, ich hätte es funktioniert, aber nach einigen schweren Einführungs / Aktualisierung kann ich sehen, dass es nicht richtig funktioniert (überhaupt).
Dies ist eine Art einer zweiteilige Frage, wäre der erste Teil sein, wie die Höhe eines Unterbaums zu berechnen, ich weiß, die Definition "Die Höhe eines Knotens die Länge des längsten Weges nach unten ist zu einem Blatt von diesem Knoten. " und ich verstehe es, aber ich kann nicht es bei der Umsetzung. Und mich zu verwirren weiter kann dieses Zitat auf Wikipedia auf Baumhöhen zu finden „Herkömmlicherweise wird der Wert -1 entspricht eine Teilstruktur ohne Knoten, während Null auf einen Teilbaum mit einem Knoten entspricht.“
Und der zweite Teil ist immer die Balance Faktor eines Unterbaums in einem AVL-Baum, habe ich kein Problem habe, das Konzept zu verstehen, "erhalten Sie die Höhe Ihrer L und R Teilbäume und subtrahiert R von L ". Und das ist definiert als so etwas wie diese: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
auf wikipedia Lesen sagt dies auf den ersten Zeilen Einfügungen in einen AVL-Baum beschreiben: "Wenn der Ausgleichsfaktor -1 wird, 0 oder 1, dann der Baum noch in AVL Form ist, und keine Drehungen sind notwendig ".
Es geht dann auf, das sagte "Wenn der Ausgleichsfaktor wird 2 oder -2 dann der Baum an diesem Knoten verwurzelt ist unausgewogen, und ein Baum Rotation benötigt wird. Allenfalls eine Einfach- oder Doppel Rotation benötigt werden den Baum zu balancieren " -., die ich keine Schwierigkeiten haben, zu erfassen.
Aber (ja, es gibt immer ein aber).
Hier wird es verwirrend, die Textzustände „Wenn sich die Balance von R 1 ist, bedeutet die Einfügung an der (äußeren) rechten Seite von diesem Knoten aufgetreten ist, und eine linke Drehung benötigt wird, um“ . Aber von m den Text zu verstehen, sagte (wie ich zitiert), dass, wenn sich die Balance innerhalb [-1, 1] war dann war es nicht nötig für den Ausgleich?
Ich fühle mich so nah bin, das Konzept zu erfassen, hat ich die Baum Umdrehungen bekommen, implementiert einen normalen binären Suchbaum und am Rande AVL-Bäume zu greifen scheint aber nur, dass wesentliche Epiphanie zu fehlen.
Edit:. Code-Beispiele sind über wissenschaftliche Formeln bevorzugt, da ich schon immer leichter zu erfassen etwas in Code hatte, aber jede Hilfe wird sehr geschätzt
Edit: Ich wünschte, ich könnte alle Antworten als „akzeptiert“ markieren, aber für mich Nicks Antwort war die erste, die ich gehen „aha“
.Lösung
Teil 1 - Höhe
Wie sagt Starblue, Höhe ist nur rekursiv. In Pseudo-Code:
height(node) = max(height(node.L), height(node.R)) + 1
Nun könnte Höhe auf zwei Arten definiert werden. Es könnte die Anzahl der Knoten in dem Pfad von der Wurzel zu diesem Knoten, oder es könnte die Anzahl der Links sein. Nach dem Seite verwiesen Sie , die häufigste Definition für die Anzahl der Links ist. In diesem Fall wird der vollständige Pseudo-Code wäre:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Wenn Sie die Anzahl der Knoten der Code wollte wäre:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
So oder so, die Neugewichtung Algorithmus Ich denke, sollte die gleiche Arbeit.
Allerdings Ihr Baum wird viel effiziente ( O (ln (n)) ), wenn Sie speichern und zu aktualisieren Höheninformationen in dem Baum, anstatt sie jedes Mal zu berechnen. ( O (n) )
Teil 2 - Ausgleich
Wenn es sagt: „Wenn du die Balance von R 1“, es spricht über den Ausgleichsfaktor des rechten Arms, wenn der Ausgleichsfaktor an der Spitze 2. ist es sagt Sie, wie zu wählen, ob eine tun einzelne Drehung oder eine Doppeldrehung. In (Python wie) Pseudo-Code:
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
Andere Tipps
-
Die Höhe wird leicht durch Rekursion implementiert, das Maximum der Höhe der Teilbäume nehmen plus eins.
-
Die "Balance von R" auf den rechten Teilbaum des Baums bezieht, die aus dem Gleichgewicht geraten ist, nehme ich an.
Sie müssen keinen Baum Tiefen im Fluge berechnen.
Sie können sie halten, wie Sie Operationen durchführen.
Darüber hinaus Sie nicht wirklich in der Tat Spur von Tiefen zu halten haben; Sie können einfach den Überblick über die Differenz zwischen dem linken und rechten Baum Tiefen halten.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
hält gerade Spur des Ausgleichsfaktors (Differenz zwischen linken und rechten Teilbäumen) ist fand ich leichter von einem Programmier POV, mit der Ausnahme, dass die Balance Faktor Aussortieren nach einer Drehung ein PITA ist ...
Hier ist eine alternative Art und Weise Höhe zu finden. Fügen Sie ein zusätzliches Attribut zu Ihrem Knoten genannt Höhe:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Nun werden wir einen einfachen Breiten ersten Durchlauf des Baumes tun, und halten Sie den Höhenwert für jeden Knoten zu aktualisieren:
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
}
Cheers,
Nun können Sie 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 entspricht, basierend auf Pfadlänge, die Sie zitieren. Diese Funktion verwendet Null, wenn die Höhe des leeren Baum.
Doch für so etwas wie ein AVL-Baum, ich glaube nicht, dass Sie die Höhe tatsächlich berechnen jedes Mal, wenn Sie es brauchen. Stattdessen wird jeder Baumknoten mit einem zusätzlichen Feld erweitert, die die Höhe des Teilbaums an diesem Knoten verwurzelten sie erinnern. Dieses Feld hat up-to-date zu halten, wie der Baum durch Einfügungen und Löschungen modifiziert wird.
Ich vermute, dass, wenn Sie die Höhe jedes Mal zu berechnen, anstatt sie in dem Baum des Cachen wie oben vorgeschlagen, dass die AVL-Baum Form richtig sein, aber es wird die erwartete logarithmische Leistung nicht hat.
Hier wird es verwirrend, der Text sagt: „Wenn du die Balance von R 1 ist, bedeutet die Einfügung an der (äußeren) rechten Seite von diesem Knoten aufgetreten ist, und eine linke Drehung benötigt wird, um“. Aber von m den Text zu verstehen, sagte (wie ich zitiert), dass, wenn sich die Balance innerhalb war [-1, 1] dann war es nicht nötig für den Ausgleich?
R ist die rechte Kind des aktuellen Knotens N.
Wenn balance(N) = +2, dann müssen Sie eine Drehung von einer Art. Aber welche Drehung zu benutzen? Nun, es hängt davon ab, balance(R): wenn balance(R) = +1 dann brauchen Sie eine Linksdrehung auf N; aber wenn balance(R) = -1 dann müssen Sie eine Doppeldrehung von einer Art.
Hier ist, wo es verwirrend, sagt der Text: „Wenn sich die Balance von R 1, es bedeutet die Einfügung an der (äußeren) rechten Seite dieses Knotens und einen linken aufgetreten Rotation benötigt wird“. Aber von m Verstehen des Textes sagte (wie ich zitiert), dass, wenn die Ausgleichsfaktor war innerhalb von [-1, 1], dann gibt es keine Notwendigkeit für den Ausgleich?
Okay, Epiphanie Zeit.
Überlegen Sie, was eine Rotation der Fall ist. Lassen Sie uns darüber nachdenken, eine Linksdrehung.
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 ist die große Sache, die Sie hier feststellen müssen - die linke Drehung HAT DEN BAUM die Tiefe nicht verändert. Wir sind nicht mehr ausgeglichen dafür getan zu haben.
Aber - und hier ist die Magie in AVL - wenn wir das richtige Kind nach rechts FIRST gedreht, was wir haben würden, ist dies ...
P
\
O
\
LC
\
RC
Und jetzt, wenn wir drehen O links, was wir bekommen, ist dies ...
P
\
LC
/ \
O RC
Magic! wir haben es geschafft, loszuwerden, ein Niveau des Baumes zu bekommen -. haben wir den Baum Balance gemacht
Balancieren der Baum mittels Über Tiefe loszuwerden, und Verpacken der oberen Ebenen mehr vollständig - das ist genau das, was wir gerade getan
.Der ganze Zeug über Einzel- / Doppeldrehungen ist einfach, dass Sie Ihre Unterstruktur haben, haben wie folgt aussehen;
P
\
O
\
LC
\
RC
, bevor Sie drehen - und Sie können ein Recht zu tun haben, drehen in diesen Zustand zu erhalten. Aber wenn Sie bereits in diesem Zustand, müssen Sie nur die linke drehen tun.
Geben Sie BinaryTree<T, Comparator>::Node ein subtreeHeight Datenelement, auf 0 in seinem Konstruktor initialisiert und aktualisiert automatisch jedes Mal 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 Datenelemente subtreeSize und depthFromRoot werden ebenfalls aktualisiert.
Diese Funktionen werden aufgerufen, wenn ein Knoten eingefügt (alle getestet), 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 zu entfernen, verwenden Sie eine andere Version von removeLeft und removeRight von subtreeSize++; mit subtreeSize--; ersetzen. Algorithmen für rotateLeft und rotateRight kann entweder ohne viel Problem angepasst werden. Folgendes wurde getestet und übergeben:
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;
}
}
Dabei steht
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
Diese BFS-ähnliche Lösung ist ziemlich einfach. Einfach Sprünge Ebene one-by-one.
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
