1. Concept
L'arbre de recherche binaire devient également un arbre de tri binaire. Il a la caractéristique que si un nœud a deux nœuds enfants, il doit être satisfait. La valeur du nœud enfant gauche doit être inférieure à la valeur du nœud, et la valeur du nœud enfant droit doit être supérieure à la valeur du nœud. Pour les comparaisons de types non basiques, l'interface du comparateur peut être implémentée. Dans cet article, les données de type int sont utilisées pour le fonctionnement.
Pour implémenter un arbre binaire, vous devez commencer par son augmentation. Ce n'est qu'en construisant l'arbre que vous pouvez utiliser d'autres opérations.
2. Construction d'un arbre de recherche binaire
Lorsque vous parlez de l'augmentation des arbres binaires, nous devons d'abord construire une classe représentant un nœud. La classe du nœud a plusieurs attributs, la valeur du nœud, le nœud parent, le nœud gauche et le nœud droit du nœud. Le code est le suivant
classe statique node {nœud parent; Node Leftchild; Node Rightchild; int Val; Node public (Node Parent, Node LeftChild, Node RightChild, int Val) {Super (); this.parent = parent; this.leftchild = Leftchild; this.RightChild = RightChild; this.val = val; } Node public (int Val) {this (null, null, null, val); } Node public (nœud nœud, int Val) {this (nœud, null, null, val); }}Ici, nous utilisons la méthode d'écriture de classe interne. Après avoir construit la valeur du nœud, nous construirons tout l'arbre. Un arbre doit d'abord avoir un nœud racine, puis s'étendre aux nœuds enfants restants. Dans cet arbre, il existe également certains attributs, tels que la racine de nœud racine de base et la taille de l'élément dans l'arbre. Si ces deux attributs sont utilisés, l'attribut de comparaison peut être ajouté ou une implémentation par défaut peut être fournie. Le code spécifique est le suivant
classe publique SearchBinaryTree {Root de nœud privé; Taille INT privée; public SearchBinaryTree () {super (); }}3. Ajouter
Lorsque vous ajoutez des éléments, vous devez considérer l'initialisation du nœud racine. Généralement, il existe deux types: lorsque le constructeur de cette classe est initialisé, la racine du nœud racine sera initialisée. La seconde consiste à ajouter le nœud racine lorsque le premier élément est ajouté. Les deux fonctionnent en théorie, mais utilisent généralement le deuxième formulaire de chargement paresseux.
Lors de l'ajout d'éléments, il y a plusieurs situations qui doivent être considérées
1. Lors de l'ajout, déterminez si la racine est initialisée. S'il n'est pas initialisé, il sera initialisé. Attribuez la valeur au nœud racine et ajoutez une seule taille.
2. Étant donné que l'arbre de recherche d'arborescence binaire satisfait que la valeur du nœud racine est supérieure au nœud gauche et plus petite que le nœud droit, la valeur insérée doit être comparée au nœud racine en premier. S'il est grand, recherchez dans le bon sous-arbre. S'il est petit, recherchez dans le sous-arbre gauche. Jusqu'à un nœud enfant.
La mise en œuvre de l'insertion ici peut adopter deux types: un, une récursivité, deux, itérative (c'est-à-dire à travers le mode boucle de boucle).
3.1. Insertion de version récursive
public boolean add (int Val) {if (root == null) {root = new node (val); taille ++; Retour Vrai; } Nœud node = getAdapternode (root, val); Nœud newNode = new nœud (val); if (node.val> val) {node.leftchild = newNode; newNode.parent = nœud; } else if (node.val <val) {node.RightChild = newNode; newNode.parent = nœud; } else {// Aucun traitement pour le moment étant} taille ++; 19 return true; } / ** * Obtenez l'insertion du nœud parent du nœud. Le nœud parent satisfait à l'un des états suivants * 1. Le nœud parent est un nœud enfant * 2. La valeur du nœud d'insertion est plus petite que le nœud parent, mais le nœud parent n'a pas de nœud enfant gauche * 3. La valeur du nœud d'insertion est plus grande que le nœud parent, mais le nœud parent n'a pas de nœud enfant droit * 4. La valeur du nœud d'insertion est égal au nœud parent. * 5. Le nœud parent est vide * Si l'un des 5 cas ci-dessus est satisfait, il s'arrêtera récursivement. * @param nœud * @param val * @return * / nœud privé getAdapternode (nœud nœud, int Val) {if (node == null) {return node; } // Insérez dans le sous-arbre gauche mais il n'y a pas de sous-arbre gauche, if (node.val> val && node.leftchild == null) {return node; } // Insérez dans le sous-arbre droit mais il n'y a pas de bon sous-arbre, renvoie également if (node.val <val && node.RightChild == null) {return node; } // Insérez dans le sous-arbre droit mais il n'y a pas de bon sous-arbre, renvoie également if (node.val <val && node.RightChild == null) {return node; } // Insérez dans le sous-arbre droit mais il n'y a pas de bon sous-arbre, renvoie également if (node.val <val && node.RightChild == null) {return node; } // insérer dans le sous-arbre droit mais il n'y a pas de bon sous-arbre, renvoie également if (node.leftchild == null && node.Rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getAdaptAnDode (node.leftchild, val); } else if (node.val <val && node.Rightchild! = null) {return getAdaptAnDode (node.RightChild, val); } else {return node; }}Utilisez la récursivité, trouvez d'abord le point final de la récursivité, puis transformez tout le problème en un sous-problème. Dans le code ci-dessus, la logique est à peu près comme celle-ci: déterminez d'abord si le nœud racine est initialisé, et s'il n'est pas initialisé, il est initialisé, et après la fin, il revient, puis utilise une fonction pour obtenir le nœud adapté. Insérez ensuite la valeur.
3.2. Version itérative
Public Boolean put (int Val) {return putval (root, val); } private booléen putVal (nœud nœud, int val) {if (node == null) {// initialiser le nœud racine node = new node (val); root = nœud; taille ++; Retour Vrai; } Nœud temp = nœud; Node P; int t; / ** * Obtenez le meilleur nœud à travers DO pendant la boucle, * / do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.Rightchild; } else {temp.val = val; retourne false; }} while (temp! = null); Nœud newNode = new nœud (p, val); if (t> 0) {p.leftchild = newNode; } else if (t <0) {P.RightChild = newNode; } taille ++; Retour Vrai; }Le principe est en fait le même que la récursivité, qui est d'obtenir le meilleur nœud et d'opérer sur ce nœud.
En termes de performances, c'est certainement la meilleure version itérative, donc en général, c'est la version itérative pour fonctionner sur les données.
4. Supprimer
On peut dire que dans le fonctionnement de l'arbre de recherche binaire, la suppression est la plus compliquée, et il y a relativement de nombreuses situations à considérer. De la manière conventionnelle, si vous supprimez un nœud dans l'arbre de recherche binaire, vous penserez certainement aux quatre situations suivantes.
1. Le nœud à supprimer n'a pas de nœuds enfants à gauche et à droite, comme indiqué dans les nœuds D, E et G dans la figure ci-dessus
2. Le nœud à supprimer n'est que le nœud enfant gauche, comme le nœud B
3. Le nœud à supprimer n'est que le bon nœud enfant, comme le nœud F
4. Le nœud à supprimer a à la fois des nœuds enfants gauche et des nœuds enfants droits, tels que A et C nœuds
Pour les trois premières situations, on peut dire qu'il est relativement simple, tandis que le quatrième est compliqué. Analysons le premier
Si tel est le cas, par exemple, si le nœud D est supprimé, le nœud enfant gauche du nœud B peut être défini sur NULL, et si le nœud G est supprimé, le nœud enfant droit du nœud F peut être défini sur NULL. Quel côté doit être réglé et voir de quel côté le nœud supprimé est situé.
La deuxième façon de supprimer le nœud B, il vous suffit de définir le nœud gauche du nœud A au nœud D et le nœud parent du nœud D à A. quel côté est défini dépend de quel côté du nœud supprimé est situé sur le nœud parent.
Le troisième type est le même que le deuxième type.
Le quatrième type, qui est un peu compliqué comme mentionné précédemment, est par exemple, pour supprimer le nœud C, définir le nœud parent du nœud F sur le nœud A, définissez le nœud gauche du nœud F sur le nœud E, définissez le nœud droit de A vers le nœud F, définissez le nœud parent de E sur le nœud F (qui est, remplacez le nœud C), et il y a un autre type, remplace directement le nœud E. Alors, lequel doit être utilisé? Si le nœud de suppression est le nœud racine, comment dois-je le supprimer?
Pour le quatrième cas, vous pouvez y penser comme ceci: trouver le nœud successeur de C ou un nœud, supprimer le nœud successeur et définir la valeur du nœud successeur sur la valeur de C ou un nœud. Complétons d'abord le concept de nœuds successeurs.
Le nœud successeur d'un nœud dans toute l'arbre doit être satisfait. Le nœud avec la plus petite valeur de l'ensemble des nœuds qui vaut le nœud est le nœud successeur. Bien sûr, il peut y avoir aucun nœud successeur.
Cependant, pour le quatrième cas, le nœud successeur doit exister et doit être dans son sous-arbre droit, et il répond également à l'un des cas où il n'y a qu'un seul nœud enfant ou pas de nœud enfant. La raison spécifique peut en être pensée, car le nœud successeur est plus grand que le nœud C, et parce que les sous-sections gauche et droite du nœud C doivent exister, il doit exister dans la sous-section gauche dans le sous-arbre droit. Par exemple, le nœud successeur de C est F, et le nœud successeur de A est E.
Avec l'analyse ci-dessus, l'implémentation est relativement simple, le code est le suivant
public boolean delete (int Val) {node node = getNode (val); if (node == null) {return false; } Nœud parent = node.parent; Node LeftChild = Node.LeftChild; Node RightChild = Node.RightChild; // Tous les nœuds parents suivants sont vides, cela signifie que le nœud supprimé est le nœud racine if (LeftChild == null && rightchild == null) {// pas de nœuds enfants if (parent! = Null) {if (parent.leftchild == nœud) {Parent.leftchild = null; } else if (Parent.RightChild == Node) {parent.RightChild = null; }} else {// Le nœud parent n'existe pas, ce qui signifie que le nœud supprimé est le nœud racine root = null; } node = null; Retour Vrai; } else if (Leftchild == null && rightchild! = null) {// seulement le nœud droit if (parent! = null && parent.val> val) {// il y a un nœud parent, et la position du nœud est le côté gauche du nœud parent parent.leftchild = droite; } else if (parent! = null && parent.val <val) {// il y a un nœud parent, et la position du nœud est le côté droit du nœud parent parent.RightChild = droitechild; } else {root = rightchild; } node = null; Retour Vrai; } else if (LeftChild! = null && droitechild == null) {// seulement le nœud gauche if (parent! = null && parent.val> val) {// il y a un nœud parent, et la position du nœud est le côté gauche du nœud parent parent.leftchild = Leftchild; } else if (parent! = null && parent.val <val) {// il y a un nœud parent, et la position du nœud est le côté droit du nœud parent parent.RightChild = LeftChild; } else {root = Leftchild; } return true; } else if (LeftChild! = null && RightChild! = null) {// Les deux nœuds enfants ont le nœud successeur = getSucCessor (node); // Dans ce cas, il doit y avoir un Node successeur int temp = successeur.val; booléen delete = delete (temp); if (delete) {node.val = temp; } successeur = null; Retour Vrai; } return false; } / ** * Trouvez le nœud successeur du nœud de nœud * 1. Déterminez d'abord si le nœud a un sous-arbre droit. Si c'est le cas, recherchez le nœud successeur du sous-arbre gauche du nœud droit. Sinon, passez à l'étape suivante * 2. Trouvez le nœud parent du nœud. Si le nœud droit du nœud parent est égal au nœud, continuez à rechercher le nœud parent * jusqu'à ce que le nœud parent soit nul ou trouve le nœud bon qui n'est pas égal au nœud. * Raison, le nœud successeur doit être plus grand que le nœud. S'il y a un sous-arbre droit, le nœud successeur doit exister dans le sous-arbre droit. C'est la raison de la première étape * S'il n'y a pas de bon sous-arbre, il peut également y avoir un nœud grand-père du nœud (c'est-à-dire le nœud parent du nœud, ou le nœud parent au-dessus du nœud parent). * Recherchez itérativement, s'il y en a, il renvoie le nœud, et s'il y a non, il renvoie null * @param nœud * @return * / nœud privé getUCCessor (nœud node) {if (node.Rightchild! = Null) {node rightchild = node.rightchild; while (reightchild.leftchild! = null) {droiteChild = droitechild.leftchild; } return rightchild; } Nœud parent = node.parent; while (parent! = null && (node == parent.RightChild)) {node = parent; parent = parent.parent; } return parent; }Pour une logique spécifique, veuillez vous référer à l'analyse ci-dessus. Je ne décrirai pas le texte ici.
En plus de cette implémentation, une autre implémentation est fournie dans l'introduction à l'algorithme.
public booléen re Support (int Val) {node node = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. Le nœud gauche n'existe pas, le nœud droit peut exister, y compris deux situations. Les deux nœuds n'existent pas et seul le nœud droit existe une transplantation (Node, Node.RightChild); } else if (node.rightchild == null) {// 2. L'enfant gauche existe et le nœud droit n'existe pas de transplantation (Node, Node.leftchild); } else {// 3. Les deux nœuds ont le nœud successeur = getSucCessor (nœud); // obtiennent le nœud nœud nœud if (successeur.parent! = node) {// Le nœud successeur existe dans le sous-arbre droit du nœud. Transplant (successeur, successeur.RightChild); // remplacer le successeur par le bon nœud enfant du successeur.RightChild = node.RightChild; // Attribuez le bon arbre enfant du nœud de nœud à la bonne position du successeur. Étape précédente} transplantation (nœud, successeur); successeur.leftchild = node.leftchild; successeur.leftchild.parent = successeur; } return true; } / ** * Remplacez le nœud enfant par le nœud nœud * @param nœud racine root * @param nœud nœud à supprimer * @param nœud enfant nœud nœud nœud enfant nœud enfant nœud enfant vide greeplant (nœud nœud, nœud enfant) {/ ** * 1. Étape * 2. Déterminez que le nœud de nœud est l'enfant du nœud parent (c'est-à-dire déterminer si le nœud est un nœud droit ou un nœud gauche), * après avoir obtenu le résultat, remplacer le nœud enfant par le nœud de nœud, c'est-à-dire que si le nœud de nœud est un nœud gauche, l'enfant sera également le nœud gauche après avoir été remplacé, sinon c'est le nœud droit * 3. Node * / if (node.parent == null) {this.root = enfant; } else if (node.parent.leftchild == node) {node.parent.leftchild = enfant; } else if (node.parent.Rightchild == node) {node.parent.RightChild = enfant; } if (child! = null) {child.parent = node.parent; }}5. Recherche
La recherche est également relativement simple, mais en fait, elle a été implémentée lorsqu'elle est ajoutée. Dans les situations réelles, cette partie peut être extraite d'une méthode distincte. Le code est le suivant
Node public getNode (int Val) {Node temp = root; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.Rightchild; } else {return temp; }} while (temp! = null); retourner null; }6. Traversé de l'arbre de recherche binaire
Après avoir compris les propriétés de l'arbre de recherche binaire, il est clair que sa traversée d'ordre intermédiaire est disposée en séquence de petite à grande. Voici le code de traversée d'ordre intermédiaire fourni ici
public void print () {print (root); } private void print (nœud root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Si la position est au milieu, alors l'ordre est au milieu. Si c'est à l'avant, c'est dans le précédent, sinon c'est une impression ultérieure (root.RightChild); }} Résumer
Ce qui précède est l'implémentation Java de la fonction d'arborescence de recherche binaire introduite par l'éditeur. J'espère que ce sera utile à tout le monde. Si vous avez des questions, laissez-moi un message. L'éditeur répondra à tout le monde à temps!