Évasement insertion d'arbre
https://stackoverflow.com/questions/2008630
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En passant par quelques exercices pour parfaire mes compétences d'arbres binaires, j'ai décidé de mettre en œuvre un arbre évasement, comme indiqué dans Wikipedia:. Splay arbre
Une chose que je ne reçois pas la partie est sur l'insertion.
Il dit:
Tout d'abord, nous cherchons x dans l'arbre de évasement. Si x n'existe pas, alors nous ne trouverons pas, mais son nœud parent y. En second lieu, nous effectuons une opération d'évasement sur y qui se déplace y à la racine de l'arbre de évasement. Troisièmement, nous insérons le nouveau nœud x en tant que root d'une manière appropriée. De cette façon, soit y est à gauche ou à droite enfant de la nouvelle racine x.
Ma question est la suivante: Le texte ci-dessus semble trop laconique par rapport aux autres exemples dans l'article, pourquoi? Il semble qu'il ya quelques pièges laissés ici. Par exemple, après le nœud évasement y jusqu'à la racine, je ne peux pas remplacer aveuglément racine avec x et y amure sur x soit comme enfant à gauche ou à droite.
Supposons que la valeur n'existe pas déjà dans l'arborescence.
J'ai cet arbre:
10
/ \
5 15
/ \ \
1 6 20
et je veux insérer 8. Avec la description ci-dessus, je vais trouver le 6 jusqu'à nœuds, et dans un arbre binaire normale, 8 serait ajouté comme un enfant droit du 6 nœuds, mais ici, je dois d'abord à évaser jusqu'à la racine 6-noeud:
6
/ \
5 10
/ \
1 15
\
20
alors l'une de ces deux sont manifestement mal:
8 8
\ /
6 6
/ \ / \
5 10 5 10
/ \ / \
1 15 1 15
\ \
20 20
6 is not greater than 8 10 is not less than 8
il me semble que la seule façon de faire la évasement d'abord, puis en ajoutant correctement la nouvelle valeur en tant que root voudrait dire que je dois vérifier les critères suivants (pour ajouter le nœud évasé que l'enfant gauche de la nouvelle racine) :
- le noeud I évasé à la racine est inférieure à la nouvelle racine (6 <8)
- l'enfant du nœud le plus à droite que j'évasé à la racine est également inférieure à la nouvelle racine (20 8)
Cependant, si je devais séparer le noeud I évasé, en prenant l'enfant droit et annexant comme l'enfant droit du nouveau nœud, je reçois ceci:
8
/ \
6 10
/ \
5 15
/ \
1 20
Mais, est-ce simple changement va toujours me donner un arbre correct? Je suis un moment difficile à venir avec un exemple, mais peut-il conduire à ce qui suit:
- La nouvelle valeur que je veux ajouter est supérieure à la racine temporaire (le noeud I évasé à la racine), mais aussi plus élevé que l'enfant du gauche droit enfant de la racine temporaire?
Ie. un arbre qui ressemblerait essentiellement comme après évasement, mais avant de remplacer la racine?
10
/ \
5 15
/ \
11 20
et je veux ajouter 13, ce qui rendrait le nouvel arbre comme ceci:
13
/ \
10 15
/ / \
5 11 20 <-- 11, on the wrong side of 13
ou cela peut-il jamais arriver?
Ma deuxième question est la suivante: Ne serait-il beaucoup plus facile de réécrire l'opération comme suit:
Tout d'abord, nous cherchons x dans l'arbre de évasement. Si x n'existe pas, alors nous ne trouverons pas, mais son nœud parent y. Ensuite, nous ajoutons le nouveau nœud soit comme un enfant à gauche ou à droite du nœud parent. En troisième lieu, nous effectuons une opération d'évasement sur le nœud nous avons ajouté qui se déplacera la nouvelle valeur à la racine de l'arbre évasement.
Souligné par l'auteur de montrer ce que je changé.
La solution
Je ne vois pas comment le problème que vous décrivez pourrait se produire. Si vous souhaitez insérer 13 dans cet arbre, vous devez d'abord trouver où il serait:
10
/ \
5 15
/ \
11 20
De 10 vous allez à droite, de 15 vous allez à gauche, de 11 vous allez à droite ... et vous n'avez pas plus d'éléments. Si 13 il avait été dans l'arbre, nous aurions trouvé comme un enfant droit de 11. Ainsi, selon la règle que nous effectuons une opération d'évasement sur 11 qui se déplacera 11 à la racine de l'arbre évasement:
11
/ \
10 15
/ \
5 20
Ensuite, nous ajoutons 13 comme la nouvelle racine, avec 11 comme l'enfant gauche:
13
/ \
11 15
/ \
10 20
/
5
Maintenant, il n'y a pas de problème.
Tout d'abord, nous cherchons x dans l'arbre de évasement. Si x n'existe pas, alors nous ne trouverons pas, mais son nœud parent y. Ensuite, nous ajoutons le nouveau nœud soit comme un enfant à gauche ou à droite du nœud parent. Troisièmement, nous effectuons une opération d'évasement sur le nœud, nous avons ajouté qui se déplacera la nouvelle valeur à la racine de l'arbre évasement.
Cela me semble que cela fonctionnerait aussi, mais si je vous, je venais d'essayer de mettre en œuvre la version telle qu'elle décrit dans Wikipedia depuis beaucoup de gens ont testé cela et il est déjà bien documenté.
Autres conseils
« Splay Tree » immédiatement m'a rappelé un article paru dans UJC je l'ai lu il y a un certain temps, vous trouverez peut-être quelques-uns il aperçu: Mise en œuvre Splay Arbre dans C.
Troisièmement, nous insérer le nouveau nœud x en tant que root d'une manière appropriée. De cette façon, soit y est à gauche ou à droite enfant de la nouvelle racine x.
Oui, mais cette nouvelle racine x doit avoir 2 enfants, c'est la raison pour laquelle cette phrase peut paraître déroutant.
le nouveau nœud serait ajouté à l'arbre comme un arbre de recherche binaire normal. Ensuite, le nouveau nœud serait évasé jusqu'à la racine ou le premier niveau de la racine. En outre, lorsque l'on insère un nouveau nœud, il faut trouver l'endroit pour le mettre, alors nous faisons une découverte. Et toutes les opérations, y compris trouver un arbre évasement déclenche une opération d'évasement. Peut-être c'est pourquoi l'article wikipedia décrit comme ça. Insérer simplement le nouveau nœud et évasement vers le haut. De toute façon l'arbre devient plus équilibrée qu'elle ne l'était. fonctionne très bien ici
