Share
Hasta ahora hemos analizado las estructuras de datos que organizan los datos de forma lineal. Las listas vinculadas contienen datos de un solo nodo de inicio a un solo nodo de terminación. Los arreglos mantienen los datos en bloques contiguos unidimensionales..
En esta sección, veremos cómo agregar una dimensión más nos permitirá introducir una nueva estructura de datos: el árbol. Específicamente, veremos un tipo de árbol conocido como árbol de búsqueda binario. Los árboles de búsqueda binarios toman la estructura general del árbol y aplican un conjunto de reglas simples que definen la estructura del árbol.
Antes de aprender sobre esas reglas, aprendamos qué es un árbol..
Un árbol es una estructura de datos donde cada nodo tiene cero o más hijos. Por ejemplo, podríamos tener un árbol como este:
Una estructura de árbol organizacional. En este árbol, podemos ver la estructura organizativa de una empresa. Los bloques representan personas o divisiones dentro de la empresa, y las líneas representan relaciones de información. Un árbol es una manera lógica y muy eficiente de presentar y almacenar esta información..
El árbol que se muestra en la figura anterior es un árbol general. Representa las relaciones padre / hijo, pero no hay reglas para la estructura. El CEO tiene un informe directo, pero podría fácilmente no tener ninguno o veinte. En la figura, las ventas se muestran a la izquierda de Marketing, pero ese orden no tiene sentido. De hecho, la única restricción observable es que cada nodo tiene como máximo un padre (y el nodo más alto, la Junta Directiva, no tiene padre).
Un árbol de búsqueda binario utiliza la misma estructura básica que el árbol general que se muestra en la última figura, pero con la adición de algunas reglas. Estas reglas son:
Veamos un árbol que está construido usando estas reglas:
Árbol de búsqueda binaria Observe cómo se aplican las restricciones que especificamos en el diagrama. Cada valor a la izquierda del nodo raíz (ocho) tiene un valor menor que ocho, y cada valor a la derecha es mayor o igual que el nodo raíz. Esta regla se aplica recursivamente en cada nodo en el camino.
Con este árbol en mente, pensemos en los pasos para construirlo. Cuando se inició el proceso, el árbol estaba vacío y luego se agregó un valor, ocho. Debido a que fue el primer valor agregado, se colocó en la posición raíz (padre principal).
No sabemos el orden exacto en que se agregaron el resto de los nodos, pero presentaré un camino posible. Los valores se agregarán usando un método llamado Añadir que acepta el valor.
Árbol BinaryTree = nuevo BinaryTree (); árbol.Add (8); árbol.Add (4); tree.Add (2); árbol.Add (3); tree.Add (10); árbol.Agregar (6); árbol.Add (7);
Veamos los primeros artículos..
Ocho se agregó primero y se convirtió en la raíz. A continuación, se añadieron cuatro. Como cuatro es menos que ocho, debe ir a la izquierda de ocho según la regla número dos. Como ocho no tiene ningún hijo a su izquierda, cuatro se convierte en el hijo de la izquierda inmediata de ocho.
Dos se añaden a continuación. Dos es menos de ocho, por lo que va hacia la izquierda. Ya hay un nodo a la izquierda de ocho, por lo que la lógica de comparación se realiza de nuevo. dos es menos de cuatro, y cuatro no tiene hijo izquierdo, por lo que dos se convierte en el hijo izquierdo de cuatro.
Tres se agregan a continuación y van a la izquierda de ocho y cuatro. Cuando se compara con los dos nodos, es más grande, por lo que tres se agregan a la derecha de dos según la regla número tres.
Este ciclo de comparación de valores en cada nodo y luego la comprobación de cada niño una y otra vez hasta que se encuentra la ranura correcta se repite para cada valor hasta que se crea la estructura de árbol final.
los BinaryTreeNode representa un solo nodo en el árbol. Contiene referencias a los elementos secundarios izquierdo y derecho (nulo si no hay ninguno), el valor del nodo y el IComparable.CompareTo Método que permite comparar los valores del nodo para determinar si el valor debe ir a la izquierda o derecha del nodo actual. Esto es todo BinaryTreeNode Como puedes ver, es muy simple..
clase BinaryTreeNode: IComparable donde TNode: IComparable public BinaryTreeNode (valor de TNode) Valor = valor; public BinaryTreeNode Left get; conjunto; public BinaryTreeNode Right get; conjunto; Valor público de TNode obtener; conjunto privado /// /// Compara el nodo actual con el valor proporcionado. /// /// El valor del nodo para comparar con /// 1 si el valor de la instancia es mayor que /// el valor proporcionado, -1 si es menor, o 0 si es igual. public int CompareTo (TNode other) return Value.CompareTo (other);
los Árbol binario La clase proporciona los métodos básicos que necesitas para manipular el árbol: Añadir, retirar, una Contiene método para determinar si un elemento existe en el árbol, varios métodos de enumeración y enumeración (estos son métodos que nos permiten enumerar los nodos en el árbol en varios órdenes bien definidos) y la normal Contar y Claro metodos.
Para inicializar el árbol, hay un BinaryTreeNode referencia que representa el nodo principal (raíz) del árbol, y hay un entero que realiza un seguimiento de cuántos elementos hay en el árbol.
public class BinaryTree: IEnumerable donde T: IComparable private BinaryTreeNode _head; int _count privado; Public void Add (valor de T) lanzar una nueva NotImplementedException (); public bool Contiene (valor T) lanzar una nueva NotImplementedException (); public bool Remove (valor de T) lanzar una nueva NotImplementedException (); public void PreOrderTraversal (Action action) throw new NotImplementedException (); public void PostOrderTraversal (Action action) throw new NotImplementedException (); public void InOrderTraversal (Action action) throw new NotImplementedException (); public IEnumerator GetEnumerator () lanza la nueva NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () lanza la nueva NotImplementedException (); public void Clear () lanza la nueva NotImplementedException (); public int Count get;
| Comportamiento | Agrega el valor proporcionado a la ubicación correcta dentro del árbol. |
| Actuación | O (log n) en promedio; O (n) en el peor de los casos. |
Agregar un nodo al árbol no es terriblemente complejo y se hace aún más fácil cuando el problema se simplifica en un algoritmo recursivo. Hay dos casos que deben ser considerados:
En el primer caso, simplemente asignamos el nuevo nodo y lo agregamos al árbol. En el segundo caso, comparamos el valor con el valor del nodo. Si el valor que intentamos agregar es menor que el valor del nodo, el algoritmo se repite para el elemento secundario izquierdo del nodo. De lo contrario, se repite para el hijo derecho del nodo..
Public void Add (valor de T) // Caso 1: el árbol está vacío. Asignar la cabeza. if (_head == null) _head = new BinaryTreeNode (value); // Caso 2: el árbol no está vacío, así que recursivamente // encuentre la ubicación correcta para insertar el nodo. else AddTo (_head, valor); _count ++; // Algoritmo de adición recursiva. AddTo privado (nodo BinaryTreeNode, valor T) // Caso 1: el valor es menor que el valor del nodo actual si (value.CompareTo (node.Value) < 0) // If there is no left child, make this the new left, if (node.Left == null) node.Left = new BinaryTreeNode(value); else // else add it to the left node. AddTo(node.Left, value); // Case 2: Value is equal to or greater than the current value. else // If there is no right, add it to the right, if (node.Right == null) node.Right = new BinaryTreeNode(value); else // else add it to the right node. AddTo(node.Right, value);
| Comportamiento | Elimina el primer nore encontrado con el valor indicado.. |
| Actuación | O (log n) en promedio; O (n) en el peor de los casos. |
Eliminar un valor del árbol es una operación conceptualmente simple que se vuelve sorprendentemente compleja en la práctica.
En un nivel alto, la operación es simple:
El primer paso es simple, y como veremos, se realiza utilizando el mismo mecanismo que utiliza el método Contains. Sin embargo, una vez que se identifica el nodo que se eliminará, la operación puede tomar una de las tres rutas dictadas por el estado del árbol alrededor del nodo que se eliminará. Los tres estados se describen en los siguientes tres casos..
Caso uno: el nodo que se va a eliminar no tiene hijo derecho.
Caso 1 El nodo a eliminar no tiene hijo derecho En este caso, la operación de eliminación puede simplemente mover el hijo izquierdo, si lo hay, al lugar del nodo eliminado. El árbol resultante se vería así:
Caso 1 - Estado del árbol después de la eliminación Caso Dos: El nodo que se eliminará tiene un hijo derecho que, a su vez, no tiene hijo izquierdo.
Caso dos El nodo a eliminar tiene un hijo derecho que no tiene hijo izquierdo En este caso, queremos mover el elemento secundario derecho del nodo eliminado (seis) al lugar del nodo eliminado. El árbol resultante se verá así:
Estado del árbol después de la eliminación Caso tres: El nodo que se eliminará tiene un hijo derecho que, a su vez, tiene un hijo izquierdo.
Caso 3: el nodo que se va a eliminar tiene un hijo derecho que tiene un hijo izquierdo En este caso, el niño más a la izquierda del niño derecho del nodo eliminado debe colocarse en la ranura del nodo eliminado.
Tomemos un minuto para pensar por qué esto es cierto. Hay dos hechos que sabemos sobre el subárbol que comienza con la eliminación del nodo (por ejemplo, el subárbol cuya raíz es el nodo con el valor cinco).
Necesitamos colocar un valor en la ranura del nodo eliminado que sea más pequeño o igual a cada nodo a su derecha. Para hacer eso, necesitamos obtener el valor más pequeño en el lado derecho. Por lo tanto necesitamos el nodo más a la izquierda del niño derecho.
Después de la eliminación del nodo, el árbol se verá así:
Caso 3 - Árbol después de la eliminación del nodo Ahora que entendemos los tres escenarios de eliminación, veamos el código para que esto suceda..
Una cosa a tener en cuenta: la FindWithParent El método (consulte la sección Contiene) devuelve el nodo que se eliminará, así como el elemento primario del nodo que se está eliminando. Esto se hace porque cuando se elimina el nodo, necesitamos actualizar el Izquierda o Derecha Propiedad para apuntar al nuevo nodo..
Podríamos evitar hacer esto si todos los nodos mantuvieran una referencia a sus padres, pero eso introduciría gastos generales de memoria por nodo y costos de contabilidad que solo son necesarios en este caso.
public bool Remove (valor T) BinaryTreeNode current, parent; // Encuentra el nodo a eliminar. current = FindWithParent (value, out parent); if (current == null) return false; _count--; // Caso 1: Si el actual no tiene hijo derecho, el izquierdo actual reemplaza al actual. if (current.Right == null) if (parent == null) _head = current.Left; else int result = parent.CompareTo (current.Value); if (resultado> 0) // Si el valor principal es mayor que el valor actual, // hace que el hijo izquierdo actual sea un hijo izquierdo de padre parent.Left = current.Left; else if (resultado < 0) // If parent value is less than current value, // make the current left child a right child of parent. parent.Right = current.Left; // Case 2: If current's right child has no left child, current's right child // replaces current. else if (current.Right.Left == null) current.Right.Left = current.Left; if (parent == null) _head = current.Right; else int result = parent.CompareTo(current.Value); if (result > 0) // Si el valor principal es mayor que el valor actual, // haga que el hijo derecho actual sea el hijo izquierdo del padre. parent.Left = current.Right; else if (resultado < 0) // If parent value is less than current value, // make the current right child a right child of parent. parent.Right = current.Right; // Case 3: If current's right child has a left child, replace current with current's // right child's left-most child. else // Find the right's left-most child. BinaryTreeNode leftmost = current.Right.Left; BinaryTreeNode leftmostParent = current.Right; while (leftmost.Left != null) leftmostParent = leftmost; leftmost = leftmost.Left; // The parent's left subtree becomes the leftmost's right subtree. leftmostParent.Left = leftmost.Right; // Assign leftmost's left and right to current's left and right children. leftmost.Left = current.Left; leftmost.Right = current.Right; if (parent == null) _head = leftmost; else int result = parent.CompareTo(current.Value); if (result > 0) // Si el valor del padre es mayor que el valor actual, // haga que el extremo izquierdo sea el hijo izquierdo del padre. parent.Left = leftmost; else if (resultado < 0) // If parent value is less than current value, // make leftmost the parent's right child. parent.Right = leftmost; return true;
| Comportamiento | Devuelve verdadero si el árbol contiene el valor proporcionado. De lo contrario, devuelve falso.. |
| Actuación | O (log n) en promedio; O (n) en el peor de los casos. |
Contiene difiere a FindWithParent, que realiza un algoritmo simple de caminar por el árbol que realiza los siguientes pasos, comenzando en el nodo principal:
Ya que Contiene devuelve un Booleano, el valor devuelto está determinado por si FindWithParent devuelve un no-nulo BinaryTreeNode (verdadero) o nulo (falso).
los FindWithParent El método de eliminación también utiliza el método. El parámetro out, parent, no es usado por Contiene.
public bool Contiene (valor T) // Aplazar la función auxiliar de búsqueda de nodos. BinaryTreeNode padre; devuelve FindWithParent (value, out parent)! = null; /// /// Busca y devuelve el primer nodo que contiene el valor especificado. Si no se encuentra el valor ///, devuelve nulo. También devuelve el padre del nodo encontrado (o nulo) /// que se usa en Eliminar. /// privado BinaryTreeNode FindWithParent (valor T, fuera de BinaryTreeNode parent) // Ahora, intente encontrar datos en el árbol. BinaryTreeNode current = _head; padre = nulo; // Si bien no tenemos una coincidencia ... while (current! = Null) int result = current.CompareTo (value); if (resultado> 0) // Si el valor es menor que el actual, vaya a la izquierda. padre = actual; current = current.Left; else if (resultado < 0) // If the value is more than current, go right. parent = current; current = current.Right; else // We have a match! break; return current;
| Comportamiento | Devuelve el número de valores en el árbol (0 si está vacío). |
| Actuación | O (1) |
El campo de conteo se incrementa por el Añadir Método y decrementado por el retirar método.
public int Count get return _count;
| Comportamiento | Elimina todos los nodos del árbol.. |
| Actuación | O (1) |
public void Clear () _head = null; _count = 0;
Los recorridos de árbol son algoritmos que permiten procesar cada valor en el árbol en un orden bien definido. Para cada uno de los algoritmos analizados, se utilizará el siguiente árbol como entrada de muestra.
Los ejemplos que siguen a todos aceptan una Acción parámetro. Este parámetro define la acción que se aplicará a cada nodo a medida que sea procesada por el recorrido.
La sección de Orden para cada recorrido indicará el orden en que atravesaría el siguiente árbol.
El árbol de muestra para resultados de ordenamiento transversal | Comportamiento | Realiza la acción provista en cada valor en preorden (vea la descripción que sigue). |
| Actuación | En) |
| Orden | 4, 2, 1, 3, 5, 7, 6, 8 |
El recorrido de la preorden procesa el nodo actual antes de moverse a la izquierda y luego a la derecha. Comenzando en el nodo raíz, cuatro, la acción se ejecuta con el valor cuatro. Luego se procesa el nodo izquierdo y todos sus elementos secundarios, seguido del nodo derecho y todos sus elementos secundarios.
Un uso común del recorrido de la preorden sería crear una copia del árbol que contenga no solo los mismos valores de nodo, sino también la misma jerarquía.
public void PreOrderTraversal (Action Action) PreOrderTraversal (action, _head); Private void PreOrderTraversal (acción, nodo BinaryTreeNode) if (node! = null) action (node.Value); PreOrderTraversal (action, node.Left); PreOrderTraversal (action, node.Right);
| Comportamiento | Realiza la acción provista en cada valor en el orden posterior (vea la descripción que sigue). |
| Actuación | En) |
| Orden | 1, 3, 2, 6, 8, 7, 5, 4 |
El recorrido posterior al pedido visita el hijo izquierdo y derecho del nodo de forma recursiva, y luego realiza la acción en el nodo actual una vez que los niños están completos.
Los recorridos posteriores al pedido a menudo se utilizan para eliminar un árbol completo, como en los lenguajes de programación donde se debe liberar cada nodo, o para eliminar subárboles. Este es el caso porque el nodo raíz se procesa (borra) por última vez y sus hijos se procesan de manera que minimice la cantidad de trabajo retirar algoritmo tiene que realizar.
public void PostOrderTraversal (Action action) PostOrderTraversal (action, _head); Private void PostOrderTraversal (acción, nodo BinaryTreeNode) if (node! = null) PostOrderTraversal (action, node.Left); PostOrderTraversal (action, node.Right); acción (node.Value);
| Comportamiento | Realiza la acción proporcionada en cada valor en en orden (ver la descripción que sigue). |
| Actuación | En) |
| Orden | 1, 2, 3, 4, 5, 6, 7, 8 |
Los procesos de recorrido en orden de los nodos en el orden de clasificación, en el ejemplo anterior, los nodos se ordenarían en orden numérico de menor a mayor. Para ello, encuentra el nodo más pequeño (el más a la izquierda) y luego lo procesa antes de procesar los nodos más grandes (a la derecha).
Los recorridos en orden se utilizan cada vez que los nodos deben procesarse en orden de clasificación.
El siguiente ejemplo muestra dos métodos diferentes para realizar un recorrido inorder. El primero implementa un enfoque recursivo que realiza una devolución de llamada para cada nodo atravesado. El segundo elimina la recursión mediante el uso de la estructura de datos de la Pila y devuelve un IEnumerador permitir la enumeración directa.
Public void InOrderTraversal (Action action) InOrderTraversal (action, _head); Private void InOrderTraversal (acción, nodo BinaryTreeNode) if (node! = null) InOrderTraversal (action, node.Left); acción (node.Value); InOrderTraversal (action, node.Right); public IEnumerator InOrderTraversal () // Este es un algoritmo no recursivo que usa una pila para demostrar la eliminación de // recursión. if (_head! = null) // Almacene los nodos que hemos omitido en esta pila (evita la recursión). Stack> stack = new Stack> (); BinaryTreeNode current = _head; // Al eliminar la recursión, debemos hacer un seguimiento de si // deberíamos ir al nodo izquierdo o los nodos derechos a continuación. bool goLeftNext = true; // Empieza presionando Head en la pila. pila.Pulgar (actual); while (stack.Count> 0) // Si nos dirigimos a la izquierda ... if (goLeftNext) // Empuje todo menos el nodo de la izquierda a la pila. // Vamos a ceder el más a la izquierda después de este bloque. while (current.Left! = null) stack.Push (current); current = current.Left; // Inorder is left-> yield-> right. Rendimiento retorno corriente.Valor; // Si podemos ir bien, hazlo. if (current.Right! = null) current = current.Right; // Una vez que hayamos girado a la derecha, debemos comenzar // a ir a la izquierda nuevamente. goLeftNext = true; else // Si no podemos ir a la derecha, entonces necesitamos arrancar el nodo principal // para poder procesarlo y luego ir a su nodo derecho. current = stack.Pop (); goLeftNext = falso;
| Comportamiento | Devuelve un enumerador que enumera utilizando el algoritmo transversal de InOrder. |
| Actuación | O (1) para devolver el enumerador. Enumerar todos los elementos es O (n). |
public IEnumerator GetEnumerator () return InOrderTraversal (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () return GetEnumerator ();
Accentsconagua