1. Concepto
El árbol de búsqueda binario también se convierte en un árbol de clasificación binario. Tiene la característica de que si un nodo tiene dos nodos infantiles, debe estar satisfecho. El valor del nodo hijo izquierdo debe ser menor que el valor del nodo, y el valor del nodo infantil derecho debe ser mayor que el valor del nodo. Para las comparaciones de tipos no básicos, se puede implementar la interfaz de comparación. En este artículo, los datos de tipo int se utilizan para la operación.
Para implementar un árbol binario, debe comenzar con su aumento. Solo construyendo el árbol puede usar otras operaciones.
2. Construcción del árbol de búsqueda binario
Al hablar sobre el aumento de los árboles binarios, primero debemos construir una clase que represente un nodo. La clase del nodo tiene varios atributos, el valor del nodo, el nodo principal, el nodo izquierdo y el nodo derecho del nodo. El código es el siguiente
nodo de clase estática {nodo parent; Nodo Leftchild; Nodo Rightchild; int val; nodo público (nodo parent, nodo leftchild, nodo rightchild, int val) {super (); this.parent = parent; this.leftchild = Leftchild; this.rightChild = RightChild; this.val = val; } nodo público (int val) {this (null, null, null, val); } nodo público (nodo nodo, int val) {this (nodo, nulo, nulo, val); }}Aquí usamos el método de escritura de clase interna. Después de construir el valor del nodo, construiremos todo el árbol. Un árbol primero debe tener un nodo raíz y luego extenderse a los nodos infantiles restantes. En este árbol, también hay algunos atributos, como la raíz básica del nodo de la raíz y el tamaño del elemento en el árbol. Si se utilizan estos dos atributos, se puede agregar el atributo de comparación o se puede proporcionar una implementación predeterminada. El código específico es el siguiente
Public Class SearchBinaryTree {Root de nodo privado; tamaño privado int; public SearchBinaryTree () {super (); }}3. Agregar
Al agregar elementos, debe considerar la inicialización del nodo raíz. En general, hay dos tipos: cuando se inicializa el constructor de esta clase, se inicializará la raíz del nodo raíz. El segundo es agregar el nodo raíz cuando se agrega el primer elemento. Ambos trabajan en teoría, pero generalmente usan la segunda forma de carga perezosa.
Al agregar elementos, hay varias situaciones que deben considerarse
1. Al agregar, determine si se inicializa la raíz. Si no se inicializa, se inicializará. Asigne el valor al nodo raíz y agregue un tamaño.
2. Debido a que el árbol de búsqueda del árbol binario satisface que el valor del nodo raíz es mayor que el nodo izquierdo y más pequeño que el nodo derecho, el valor insertado debe compararse primero con el nodo raíz. Si es grande, busque en el subárbol correcto. Si es pequeño, busque en el subárbol izquierdo. Hasta un nodo niño.
La implementación de inserción aquí puede adoptar dos tipos: uno, recursión, dos, iterativo (es decir, a través del modo de bucle).
3.1. Inserción de la versión recursiva
public boolean add (int val) {if (root == null) {root = new nodo (val); tamaño ++; devolver verdadero; } Nodo nodo = getAdapternode (root, val); Nodo newnode = nuevo nodo (val); if (node.val> val) {node.leftchild = newnode; newnode.parent = node; } else if (node.val <val) {node.rightChild = newnode; newnode.parent = node; } else {// sin procesamiento para el tiempo} size ++; 19 return true; } /*** Obtenga el nodo principal del nodo a insertar. El nodo principal satisface uno de los siguientes estados* 1. El nodo principal es un nodo infantil* 2. El valor del nodo de inserción es menor que el nodo principal, pero el nodo principal no tiene un nodo hijo izquierdo* 3. El valor del nodo de inserción es mayor que el nodo principal, pero el nodo principal no tiene un nodo infantil derecho* 4. El valor del nodo de la inserción es igual al nodo al nodo. * 5. El nodo principal está vacío* Si uno de los 5 casos anteriores está satisfecho, se detendrá de manera recursiva. * @param nodo * @param val * @return */ private node getAdapternode (nodo nodo, int val) {if (node == null) {return node; } // Inserte en el subárbol izquierdo pero no hay subárbol izquierdo, if (node.val> val && node.leftchild == null) {return node; } // Inserte en el subárbol derecho pero no hay subtree correcto, también return if (node.val <val && node.rightchild == null) {return node; } // Inserte en el subárbol derecho pero no hay subtree correcto, también return if (node.val <val && node.rightchild == null) {return node; } // Inserte en el subárbol derecho pero no hay subtree correcto, también return if (node.val <val && node.rightchild == null) {return node; } // Inserte en el subárbol derecho pero no hay un subárbol correcto, también return if (node.leftchild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getAdapTarnode (node.leftchild, val); } else if (node.val <val && node.rightchild! = null) {return getAdapTarnode (node.rightchild, val); } else {nodo return; }}Use la recursión, primero encuentre el punto final de la recursión y luego convierta todo el problema en un subproblema. En el código anterior, la lógica es más o menos así: primero determine si el nodo raíz se inicializa y, si no se inicializa, se inicializa y, después de la finalización, regresa y luego usa una función para obtener el nodo adaptado. Luego inserte el valor.
3.2. Versión iterativa
public boolean put (int val) {return putval (root, val); } Private Boolean PutVal (nodo de nodo, int val) {if (node == null) {// inicializa el nodo del nodo raíz = nuevo nodo (val); raíz = nodo; tamaño ++; devolver verdadero; } Nodo temp = nodo; Nodo p; int t; / ** * Obtenga el mejor nodo a través de la iteración de bucle, */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {temp.val = val; devolver falso; }} while (temp! = null); Nodo newnode = nuevo nodo (p, val); if (t> 0) {p.leftchild = newnode; } else if (t <0) {p.rightChild = newnode; } tamaño ++; devolver verdadero; }El principio es en realidad el mismo que la recursión, que es obtener el mejor nodo y operar en ese nodo.
En términos de rendimiento, definitivamente es la mejor versión iterativa, por lo que, en general, es la versión iterativa de operar en los datos.
4. Eliminar
Se puede decir que en la operación del árbol de búsqueda binario, la eliminación es la más complicada, y hay relativamente muchas situaciones a considerar. De la manera convencional, si elimina un nodo en el árbol de búsqueda binario, definitivamente pensará en las siguientes cuatro situaciones.
1. El nodo a eliminar no tiene nodos infantiles izquierdo y derecho, como se muestra en los nodos D, E y G en la figura anterior
2. El nodo a eliminar es solo el nodo infantil izquierdo, como el nodo B
3. El nodo a eliminar es solo el nodo infantil correcto, como el nodo F
4. El nodo que se eliminará tiene nodos infantiles izquierdos y nodos infantiles derecho, como nodos A y C
Para las primeras tres situaciones, se puede decir que es relativamente simple, mientras que la cuarta es complicada. Analicemos el primero
Si este es el caso, por ejemplo, si se elimina el nodo D, el nodo infantil izquierdo del nodo B se puede configurar en NULL, y si el nodo G se elimina, el nodo infantil del nodo F correcto se puede establecer en NULL. Qué lado debe establecerse y ver qué lado se encuentra el nodo eliminado.
La segunda forma de eliminar el nodo B, solo necesita establecer el nodo izquierdo del nodo A al nodo D y el nodo principal del nodo D a A. qué lado se establece depende del lado del nodo eliminado en el nodo principal.
El tercer tipo es el mismo que el segundo tipo.
El cuarto tipo, que es un poco complicado como se mencionó anteriormente, es, por ejemplo, para eliminar el nodo C, establecer el nodo principal del nodo F en el nodo A, establecer el nodo izquierdo del nodo F en el nodo E, establecer el nodo derecho de A al nodo F, establecer el nodo principal de E en el nodo F (es decir, reemplazar el nodo F F), y hay otro tipo, reemplaza directamente el nodo E. Entonces, ¿cuál debe usarse? Si el nodo Delete es el nodo raíz, ¿cómo debo eliminarlo?
Para el cuarto caso, puede pensarlo así: encuentre el nodo sucesor de C o un nodo, elimine el nodo sucesor y establece el valor del nodo sucesor al valor de C o un nodo. Primero complementemos el concepto de nodos sucesores.
El nodo sucesor de un nodo en todo el árbol debe estar satisfecho. El nodo con el valor más pequeño en el conjunto de nodos que vale el nodo es el nodo sucesor. Por supuesto, puede que no haya nodos sucesores.
Sin embargo, para el cuarto caso, el nodo sucesor debe existir y debe estar en su subárbol derecho, y también cumple con uno de los casos en los que solo hay un nodo infantil o ningún nodo secundario. La razón específica se puede pensar en esto, porque el nodo sucesor es más grande que el nodo C, y debido a que las subsecciones izquierda y derecha del nodo C deben existir, debe existir en la subsección izquierda en el subree derecho. Por ejemplo, el nodo sucesor de C es F, y el nodo sucesor de A E.
Con el análisis anterior, la implementación es relativamente simple, el código es el siguiente
public boolean delete (int val) {nodo nodo = getNode (val); if (node == null) {return false; } Nodo parent = node.parent; Nodo leftchild = node.leftchild; Nodo rightchild = node.rightchild; // todos los siguientes nodos principales están vacíos, significa que el nodo eliminado es el nodo raíz if (leftchild == null && rightchild == null) {// no nodos infantiles if (parent! = Null) {if (parent.leftchild == nodo) {parent.leftchild = null; } else if (parent.rightchild == nodo) {parent.rightchild = null; }} else {// El nodo principal no existe, lo que significa que el nodo eliminado es el nodo raíz root = null; } nodo = nulo; devolver verdadero; } else if (leftchild == null && rightchild! = null) {// Solo el nodo derecho if (parent! = null && parent.val> val) {// Hay un nodo principal, y la posición del nodo es el lado izquierdo del nodo parent.leftchild = rightchild; } else if (parent! = null && parent.val <val) {// Hay un nodo principal, y la posición del nodo es el lado derecho del nodo principal. } else {root = rightchild; } nodo = nulo; devolver verdadero; } else if (LeftChild! = null && rightchild == null) {// Solo el nodo izquierdo if (parent! = null && parent.val> val) {// Hay un nodo principal, y la posición del nodo es el lado izquierdo del nodo parent.leftchild = Leftchild; } else if (parent! = null && parent.val <val) {// Hay un nodo principal, y la posición del nodo es el lado derecho del nodo principal. } else {root = LeftChild; } return verdadero; } else if (LeftChild! = NULL && RightChild! = NULL) {// Ambos nodos infantiles tienen Node Sucesor = GetSuccessor (nodo); // En este caso, debe haber un nodo sucesor int temp = Sucesor.val; boolean delete = eliminar (temp); if (eliminar) {node.val = temp; } sucesor = nulo; devolver verdadero; } return false; } /*** Encuentre el nodo sucesor del nodo del nodo* 1. Primero determine si el nodo tiene un subárbol correcto. Si es así, busque el nodo sucesor desde el subárbol izquierdo del nodo derecho. Si no, continúe con el siguiente paso* 2. Encuentre el nodo principal del nodo. Si el nodo derecho del nodo principal es igual al nodo, continúe buscando el nodo principal * hasta que el nodo principal esté nulo o encuentre el nodo derecho que no sea igual al nodo. * Razón, el nodo sucesor debe ser más grande que el nodo. Si hay un subárbol correcto, el nodo sucesor debe existir en el subárbol correcto. Esta es la razón del primer paso* Si no hay un subárbol correcto, también puede haber un nodo de abuelo del nodo (es decir, el nodo principal del nodo o el nodo principal por encima del nodo principal). * Búscalo iterativamente, si lo hay, devuelve el nodo, y si no hay, devuelve nulo * @param nodo * @return */ private node getSuccessor (nodo nodo) {if (node.right! = Null) {node rightchild = node.rightchild; while (rightchild.leftchild! = null) {rightchild = rightchild.leftchild; } return rightchild; } Nodo parent = node.parent; while (parent! = null && (node == parent.rightchild)) {node = parent; parent = parent.parent; } return parent; }Para una lógica específica, consulte el análisis anterior. No describiré el texto aquí.
Además de esta implementación, se proporciona otra implementación en la introducción al algoritmo.
Public boolean remove (int val) {nodo nodo = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. El nodo izquierdo no existe, el nodo derecho puede existir, incluidas dos situaciones. Ambos nodos no existen y solo el nodo derecho existe trasplante (nodo, nodo.rightchild); } else if (node.rightchild == null) {// 2. El niño izquierdo existe, y el nodo derecho no existe trasplante (nodo, node.leftchild); } else {// 3. Ambos nodos tienen nodo sucesor = getSuccessor (nodo); // Obtener el nodo de nodo nodo if (sucesor.parent! = nodo) {// El nodo sucesor existe en el subárbol correcto del nodo. Transplant (sucesor, sucesor.rightchild); // reemplazar el sucesor con el nodo infantil correcto del sucesor.rightChild = node.rightchild; // Asigne el árbol infantil correcto del nodo del nodo al nodo correcto del sucesor, es decir, similar al sucesor y el nodo de nodo a la posición de reemplazo del sucesor.rindchild.parrent = sucesor; trasplante (nodo, sucesor); sucesor.leftchild = node.leftchild; sucesor.leftchild.parent = sucesor; } return verdadero; } /*** Reemplace el nodo infantil con nodo de nodo* @param nodo raíz raíz* @param nodo nodo para eliminar* @param nodo niño nodo niño nodo niño nodo niño nodo niño nodo niño nodo void transplant (nodo nodo, nodo niño) { /*** 1. Primero, primero determine si el nodo tiene un nodo principal* 1. step* 2. Determine that the node node is the child of the parent node (that is, determine whether the node is a right node or a left node), * After obtaining the result, replace the child node with node node, that is, if the node node is a left node, child will also be the left node after being replaced, otherwise it is the right node* 3. Set the parent node of the node node as the parent node of the child nodo*/ if (node.parent == null) {this.root = child; } else if (node.parent.leftchild == nodo) {node.parent.leftchild = child; } else if (node.parent.rightchild == nodo) {node.parent.rightchild = child; } if (child! = null) {child.parent = node.parent; }}5. Buscar
La búsqueda también es relativamente simple, pero de hecho, se ha implementado cuando se agrega. En situaciones reales, esta parte se puede extraer de un método separado. El código es el siguiente
Public Node getNode (int val) {nodo 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); regresar nulo; }6. Traversal del árbol de búsqueda binaria
Después de comprender las propiedades del árbol de búsqueda binaria, está claro que su recorrido de orden intermedio está dispuesto en secuencia de pequeño a grande. Aquí está el código de transversal de orden intermedio proporcionado aquí
public void print () {print (root); } private void print (root nodo) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Si la posición está en el medio, entonces el orden está en el medio. Si está en el frente, está en el precedente, de lo contrario es una impresión posterior (raíz. }} Resumir
Lo anterior es la implementación de Java de la función de árbol de búsqueda binaria introducida por el editor. Espero que sea útil para todos. Si tiene alguna pregunta, déjame un mensaje. ¡El editor responderá a todos a tiempo!