La meilleure façon de calculer la hauteur dans un arbre de recherche binaire? (Équilibre un AVL-arbre)
https://stackoverflow.com/questions/575772
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je cherche la meilleure façon de calculer un équilibre nœuds dans un AVL-tree . Je pensais que je l'avais travailler, mais après quelques encartage / mise à jour lourde, je vois que cela ne fonctionne pas correctement (du tout).
est en quelque sorte une question en deux parties, la première partie serait comment calculer la hauteur d'un sous-arbre, je sais que la définition "La hauteur d'un nœud est la longueur du plus long chemin vers le bas à une feuille de ce noeud. " et je le comprends, mais je ne à sa mise en œuvre. Et pour me embrouiller davantage cette citation peut être trouvée sur wikipedia sur les hauteurs d'arbres « Classiquement, la valeur -1 correspond à un sous-arbre sans noeuds, alors que zéro correspond à un sous-arbre avec un noeud. »
Et la deuxième partie devient le facteur d'équilibre d'un sous-arbre dans un arbre AVL, j'ai pas mal à comprendre le concept, "obtenir la hauteur de vos L et R sous-arbres et soustrayez R de L ". Et cela est défini comme quelque chose comme ceci: BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]
Lecture sur wikipedia dit ceci sur les premières lignes décrivant les insertions dans un arbre AVL: «Si le facteur d'équilibre devient -1, 0 ou 1, puis l'arbre est encore sous forme AVL, et aucune rotation sont nécessaires ».
Il va ensuite, en disant cela "Si le facteur d'équilibre devient 2 ou -2 alors l'arbre dont la racine à ce nœud est déséquilibré, et une rotation des arbres est nécessaire. Tout au plus une rotation simple ou double sera nécessaire pour équilibrer l'arbre " -. que je n'ai pas du mal à saisir.
Mais (oui, il y a toujours un mais).
Voilà où cela devient confus, les états de texte « Si le facteur d'équilibre de R est 1, cela signifie que l'insertion a eu lieu sur le (externe) côté droit de ce noeud et une rotation à gauche est nécessaire » . Mais de m compréhension du texte dit (comme je l'ai cité) que si le facteur d'équilibre était à [-1, 1] alors il n'y avait pas besoin d'équilibre?
Je sens que je suis si proche de saisir le concept, j'ai obtenu les rotations des arbres vers le bas, mis en œuvre un arbre de recherche binaire normal et au bord de saisir AVL arbres mais ne manquer que épiphanie essentiel.
Edit:. Les exemples de code sont préférables aux formules académiques comme je l'ai toujours eu un temps plus facile de saisir quelque chose dans le code, mais toute aide est grandement appréciée
Modifier Je voudrais pouvoir marquer toutes les réponses que « accepté », mais pour moi la réponse de NIck était la première qui m'a fait aller « aha »
.La solution
Partie 1 - hauteur
Comme starblue dit, la taille est juste récursive. En pseudo-code:
height(node) = max(height(node.L), height(node.R)) + 1
hauteur peut être définie de deux façons. Il pourrait être le nombre de nœuds dans le chemin de la racine à ce nœud, ou il pourrait être le nombre de liens. Selon la page vous avez fait référence , la définition la plus commune est le nombre de liens. Dans ce cas, le code pseudo complet serait:
height(node):
if node == null:
return -1
else:
return max(height(node.L), height(node.R)) + 1
Si vous voulez que le nombre de noeuds du code serait:
height(node):
if node == null:
return 0
else:
return max(height(node.L), height(node.R)) + 1
De toute façon, l'algorithme de rééquilibrage je pense devrait fonctionner même.
Cependant, votre arbre sera beaucoup plus efficace ( O (ln (n)) ) si vous stockez et des informations de hauteur de mise à jour dans l'arbre, plutôt que de calculer chaque fois. ( O (n) )
Partie 2 - Mise en balance
Quand il dit: « Si le facteur d'équilibre de R est 1 », il parle du facteur d'équilibre de la branche droite, lorsque le facteur d'équilibre en haut est 2. Il vous dit comment choisir de faire un rotation unique ou une double rotation. En (python similaires) 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
J'espère que ce sens
Autres conseils
-
La hauteur est facilement mis en œuvre par récursion, prendre le maximum de la hauteur des sous-arbres plus un.
-
Le « facteur d'équilibre de R » fait référence à la sous-arbre droit de l'arbre qui est hors de l'équilibre, je suppose.
Vous n'avez pas besoin de calculer les profondeurs d'arbres à la volée.
Vous pouvez les maintenir pendant que vous effectuez des opérations.
En outre, vous ne pas vraiment en fait devez maintenir une trace de profondeur; vous pouvez simplement garder une trace de la différence entre les profondeurs des arbres à gauche et à droite.
http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Il suffit de garder la trace du facteur d'équilibre (différence entre les sous-arbres gauche et à droite) est que je trouve plus facile d'un POV de programmation, sauf que le tri le facteur d'équilibre après une rotation est un PITA ...
Voici une autre façon de trouver la hauteur. Ajouter un attribut supplémentaire à votre nœud appelé hauteur:
class Node
{
data value; //data is a custom data type
node right;
node left;
int height;
}
Maintenant, nous allons faire un simple parcours en largeur de l'arbre, et constamment mettre à jour la valeur de hauteur pour chaque noeud:
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,
Eh bien, vous pouvez calculer la hauteur d'un arbre avec la fonction récursive suivante:
int height(struct tree *t) {
if (t == NULL)
return 0;
else
return max(height(t->left), height(t->right)) + 1;
}
avec une définition appropriée de max() et struct tree. Vous devez prendre le temps de comprendre pourquoi cela correspond à la définition basée sur le chemin de longueur que vous citez. Cette fonction utilise zéro à la hauteur de l'arbre vide.
Cependant, quelque chose comme un arbre AVL, je ne pense pas que vous calculer réellement la hauteur à chaque fois que vous en avez besoin. Au lieu de cela, chaque nœud d'arbre est augmenté avec un champ supplémentaire qui se souvient de la hauteur du sous-arbre enraciné à ce noeud. Ce champ doit être tenues à jour que l'arbre est modifiée par des insertions et des suppressions.
Je soupçonne que, si vous calculez la hauteur à chaque fois au lieu de mettre en cache dans l'arbre comme suggéré ci-dessus, que la forme de l'arbre AVL sera correct, mais il n'y aura pas la performance logarithmique attendue.
Voici où il obtient confusion, le texte indique « Si le facteur d'équilibre de R est 1, cela signifie que l'insertion a eu lieu sur la droite (externe) côté de ce noeud et une rotation à gauche est nécessaire ». Mais de m compréhension du texte dit (comme je l'ai cité) que si le facteur d'équilibre était à [-1, 1] alors il n'y avait pas besoin d'équilibre?
R est l'enfant de droite du noeud courant N.
Si balance(N) = +2, alors vous avez besoin d'une rotation de quelque sorte. Mais cette rotation à utiliser? Eh bien, cela dépend de balance(R): si balance(R) = +1 alors vous avez besoin d'une rotation gauche sur N; mais si balance(R) = -1 alors vous aurez besoin d'un double rotation de quelque sorte.
est ici où il obtient confusion, le texte indique « Si le facteur d'équilibre de R est 1, il signifie l'insertion a eu lieu sur le côté droit (externe) de ce noeud et à gauche la rotation est nécessaire ». Mais de m compréhension du texte dit (comme je l'ai cité) que si le facteur d'équilibre était à [-1, 1] alors il n'y avait pas besoin d'équilibre?
Bon, le temps épiphanie.
Pensez à ce que la rotation ne. Réfléchissons une rotation gauche.
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
Maintenant, la grande chose que vous devez remarquer ici - cette rotation gauche n'a pas modifié la profondeur de l'arbre. Nous ne sommes plus équilibrée pour l'avoir fait.
Mais - et voici la magie AVL - si nous avons tourné l'enfant le droit à la première à droite, ce que nous aurions est-ce ...
P
\
O
\
LC
\
RC
Et maintenant, si on tourne O à gauche, ce que nous obtenons est-ce ...
P
\
LC
/ \
O RC
Magie! nous avons réussi à se débarrasser d'un niveau de l'arbre -. nous avons fait l'équilibre de l'arbre
Équilibrer les moyens d'arbres se débarrasser de l'excès de profondeur, et le conditionnement des niveaux supérieurs plus complètement - ce qui est exactement ce que nous venons de faire
.Toute cette substance sur les simples / doubles rotations est tout simplement que vous devez avoir votre sous-arbre qui ressemble à ceci:
P
\
O
\
LC
\
RC
avant de tourner - et vous pourriez avoir à faire un droit tourner pour entrer dans cet état. Mais si vous êtes déjà dans cet état, il vous suffit de faire la rotation vers la gauche.
Donner BinaryTree<T, Comparator>::Node un membre de données subtreeHeight, initialisé à 0 dans son constructeur, et mettre à jour automatiquement à chaque fois avec:
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;
}
}
Notez que les membres de données subtreeSize et depthFromRoot sont également mis à jour.
Ces fonctions sont appelées lors de l'insertion d'un noeud (tous testés), par exemple.
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;
}
Si la suppression d'un nœud, utilisez une autre version de removeLeft et removeRight en remplaçant subtreeSize++; avec subtreeSize--;. Les algorithmes pour rotateLeft et rotateRight peuvent être adaptés soit sans trop de problème. Ce qui suit a été testé et passé:
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;
}
}
où
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);
}
Voici le code entier: http://ideone.com/d6arrv
Cette solution BFS-like est assez simple. sauts simplement les niveaux un par un.
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
