15,590 lecturas

Cómo insertar un árbol binario en Rust

por Daw-Chih Liou2022/01/14

Demasiado Largo; Para Leer

🌳 Implementaremos un árbol binario juntos. 🧑‍🌾 Discutiremos un par de formas de insertar un nodo en un árbol binario. 🧑‍🔬 Discutiremos la propiedad de Rust en acción. ✨ Hablaremos de más funciones y sintaxis en Rust.

Companies Mentioned

featured image - Cómo insertar un árbol binario en Rust

TL;RD

🌳 Implementaremos un árbol binario juntos.
🧑‍🌾 Discutiremos un par de formas de insertar un nodo en un árbol binario.
🧑‍🔬 Discutiremos la propiedad de Rust en acción.
✨ Hablaremos de más características y sintaxis en Rust.

Estaba luchando mucho con la propiedad de Rust cuando implementé un árbol binario, así que giré y volví a leer sobre él. Después de tomarme mi tiempo para comprenderlo y refactorizar mi código, finalmente logré un gran avance. Estoy muy emocionado de compartir con ustedes las increíbles funciones que encontré en Rust. Verá conceptos interesantes como punteros inteligentes y propiedad.

¡Consigámoslo!

Estructura de datos

A Árbol binario la estructura de datos se ve así:

Cada nodo no tiene más de dos nodos secundarios. Nos referimos a ellos como niño left y niño right . Podemos traducir la descripción a código Rust así:

 pub struct BinaryTree<T> { pub value: T, pub left: Option<Box<BinaryTree<T>>>, pub right: Option<Box<BinaryTree<T>>>, }

La estructura BinaryTree contiene un valor con el tipo genérico T . Usamos Option enum para representar que el hijo left y right son opcionales.

Una Option<T> es Some que contiene un valor del tipo T o None que representa que no lo contiene. Debido a que estamos usando Option para expresar si un valor es algo o nada, el compilador de Rust puede verificar si manejamos todos los casos. para prevenir errores . En comparación con JavaScript, donde usamos un valor null para expresar el mismo concepto, Option me anima a manejar los casos de uso por adelantado y me ahorra muchos problemas en el tiempo de ejecución.

The Box es uno de los punteros inteligentes. Guarda una dirección que apunta a datos en la memoria. Box nos ayuda a crear una estructura BinaryTree con un tamaño desconocido para que podamos hacer crecer el árbol binario insertando nodos sin pensar de antemano cuántos nodos tendremos al crear el árbol.

Gestión de la memoria es una de las razones por las que Rust es tan eficaz e interesante de aprender.

Inserción

Antes de insertar un nuevo nodo de árbol binario, debemos crear una raíz. Vamos a implementarlo:

 impl<T> BinaryTree<T> { pub fn new(value: T) -> Self { BinaryTree { value, left: None, right: None, } } }

el new función asociada toma el valor de T y devuelve un BinaryTree que contiene el valor y ningún nodo secundario.

Ahora que podemos usar BinaryTree::new para crear un nodo raíz, podemos pensar en cómo insertar nodos secundarios. Intuitivamente, sería genial si pudiéramos insertar el nodo secundario izquierdo o derecho llamando a métodos en la instancia del nodo raíz. Como esto:

 BinaryTree::new(1) .left(BinaryTree::new(2)) .right(BinaryTree::new(3))

Por suerte, encontré un Excelente artículo de mi amigo en trivago, Matías , explicando exactamente cómo implementarlo.

 impl<T> BinaryTree<T> { pub fn new(value: T) -> Self { BinaryTree { value, left: None, right: None, } } pub fn left(mut self, node: BinaryTree<T>) -> Self { self.left = Some(Box::new(node)); self } pub fn right(mut self, node: BinaryTree<T>) -> Self { self.right = Some(Box::new(node)); self } }

Ahora escribamos algunas pruebas para asegurarnos de que las funciones asociadas funcionen:

 #[cfg(test)] mod tests { use super::*; #[test] fn create_new_tree() { let tree = BinaryTree::new(1); assert_eq!(tree.value, 1); } #[test] fn insert_left() { let tree = BinaryTree::new(1).left(BinaryTree::new(2)); if let Some(node) = tree.left { assert_eq!(node.value, 2); } assert_eq!(tree.right, None); } #[test] fn insert_right() { let tree = BinaryTree::new(1).right(BinaryTree::new(2)); if let Some(node) = tree.right { assert_eq!(node.value, 2); } assert_eq!(tree.left, None); } }

🥳

Inserción primero en amplitud

Los métodos de inserción son muy flexibles y podemos crear fácilmente un árbol en unas pocas líneas:

 BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3))

El código crea un árbol binario como este:

Me hizo pensar.

Si solo quiero crear un árbol binario equilibrado sin ningún otro requisito, ¿puedo insertar un nodo y el árbol encuentra el siguiente lugar disponible para mí?

Algo como esto:

 let mut root = BinaryTree::new(1); root.insert(2); root.insert(3); root.insert(4); root.insert(5);

Y crea la misma estructura de árbol que vimos arriba.

Podemos lograrlo atravesando el árbol en el primero en anchura fashion e insertando un nodo tan pronto como encontremos un nodo hijo ausente.

La forma más fácil de implementar un recorrido de respiración primero es con un Cola . Rust tiene un VecDequeue en la biblioteca estándar que podemos usar.

 pub fn insert(&mut self, new_value: T) { let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new(); queue.push_front(self); loop { let BinaryTree { ref mut left, ref mut right, .. } = queue.pop_back().unwrap(); match left { Some(node) => { queue.push_front(node); } None => { *left = Some(Box::new(BinaryTree::new(new_value))); return; } } match right { Some(node) => { queue.push_front(node); } None => { *right = Some(Box::new(BinaryTree::new(new_value))); return; } } } }

El algoritmo obliga al ciclo a visitar primero los nodos hermanos, de izquierda a derecha, antes de visitar la siguiente capa de nodos secundarios. En cada iteración, verificaremos si el hijo left o right está ausente. Si encontramos uno, ese es el próximo lugar disponible para el nuevo nodo.

Es un algoritmo bastante sencillo, pero Luché para hacerlo bien . el problema era que no entendía propiedad en Rust .

Repasemos juntos el método de insert .

Lo primero que queremos decidir es cómo queremos usar el primer argumento self . self se refiere a la instancia de BinaryTree a la que se llama el método. Lo que necesitamos de nosotros self es poder mutar el nodo secundario left y right para que podamos insertar un nuevo nodo. Simplemente pasar una referencia mutable &mut self hará el trabajo porque el método no necesita tomar posesión de self .

Para el tipo de datos del elemento VecDeque , podemos usar el mismo tipo de datos que self para almacenar referencias mutables de BinaryTree .

Al hacer estallar la cola dentro del ciclo, queremos usar una referencia mutable a left y right porque queremos insertar el nuevo nodo.

Al insertar el nuevo nodo, desreferencia la left y la right para permitir la asignación de nuevos nodos, así: *left = Some(Box::new(BinaryTree::new(new_value))) .

Me tomó algún tiempo descubrir cómo tomar prestados o mover los datos en el método. Una vez que lo conseguí, ¡tuvo tanto sentido!

Escribamos algunas pruebas para ello 🧑‍🔬

 #[test] fn insert() { let mut tree = BinaryTree::new(1); tree.insert(2); tree.insert(3); tree.insert(4); tree.insert(5); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3)) ); tree.insert(6); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3).left(BinaryTree::new(6))) ) }

Si ejecutamos las pruebas, verá un mensaje de error como este:

Es porque los árboles no se podían comparar entre sí. Podemos solucionarlo agregando el rasgo PartialEq a la estructura BinaryTree .

 + #[derive(PartialEq)] pub struct BinaryTree<T> { pub value: T, pub left: Option<Box<BinaryTree<T>>>, pub right: Option<Box<BinaryTree<T>>>, }

🥳

Conversión de matriz en árbol binario

Ahora que tenemos una inserción automática con el método de insert , podemos considerar crear un árbol equilibrado de manera más conveniente. Por ejemplo, quiero tener algo similar a Vec::from : una función asociada BinaryTree::from que toma una matriz y devuelve un BinaryTree equilibrado.

Escribamos una prueba para visualizar mejor el caso de uso:

 #[test] fn create_new_tree_with_from() { // `BinaryTree::from` takes in a reference of an array because borrowing is sufficient let tree = BinaryTree::from(&[1, 2, 3, 4, 5, 6]); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3).left(BinaryTree::new(6))) ) }

Para implementar BinaryTree::from , podemos iterar a través de la matriz y usar el método de insert para crear la estructura de árbol.

 impl<T> BinaryTree<T> { pub fn from(new_values: &[T]) -> Self { let (first, rest) = new_values.split_first().unwrap(); let mut root: BinaryTree<T> = BinaryTree::new(*first); for value in rest { root.insert(*value) } root } }

En la función, creamos un nodo raíz a partir del primer elemento de la matriz y luego insertamos el resto del elemento en el árbol uno por uno.

Si intenta probarlo, verá un mensaje de error como este:

Podemos arreglarlo especificando que el tipo T implementa el rasgo Copy .

 - impl<T> BinaryTree<T> { + impl<T> BinaryTree<T> + where + T: Copy, + {

La razón es que el método de insert en realidad toma posesión de new_value . Para mantener la memoria del programa guardada, el compilador no nos permitió "mover" los elementos del arreglo al método de insert porque el arreglo podría estar referenciado en otras partes del programa. Entonces, lo que podemos hacer es pasar una copia (duplicado) de un elemento de matriz.

¡Ahora debería funcionar!

Pensamientos finales

¡Eso es todo! La implementación completa de nuestra afirmación de árbol binario está aquí⬇️

 #[derive(Debug, PartialEq)] pub struct BinaryTree<T> { pub value: T, pub left: Option<Box<BinaryTree<T>>>, pub right: Option<Box<BinaryTree<T>>>, } impl<T> BinaryTree<T> where T: Copy, { /// /// Create a new Binary Tree node. /// pub fn new(value: T) -> Self { BinaryTree { value, left: None, right: None, } } /// /// Create a balanced tree from an array reference. /// pub fn from(new_values: &[T]) -> Self { let (first, rest) = new_values.split_first().unwrap(); let mut root: BinaryTree<T> = BinaryTree::new(*first); for value in rest { root.insert(*value) } root } /// /// Insert a tree node in the next available branch with breadth first traversal. /// pub fn insert(&mut self, new_value: T) { let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new(); queue.push_front(self); loop { let BinaryTree { ref mut left, ref mut right, .. } = queue.pop_back().unwrap(); match left { Some(node) => { queue.push_front(node); } None => { *left = Some(Box::new(BinaryTree::new(new_value))); return; } } match right { Some(node) => { queue.push_front(node); } None => { *right = Some(Box::new(BinaryTree::new(new_value))); return; } } } } /// /// Insert a left child node. /// pub fn left(mut self, node: BinaryTree<T>) -> Self { self.left = Some(Box::new(node)); self } /// /// Insert a right child node. /// pub fn right(mut self, node: BinaryTree<T>) -> Self { self.right = Some(Box::new(node)); self } } #[cfg(test)] mod tests { use super::*; #[test] fn create_new_tree() { let tree = BinaryTree::new(1); assert_eq!(tree.value, 1); } #[test] fn insert_left() { let tree = BinaryTree::new(1).left(BinaryTree::new(2)); if let Some(node) = tree.left { assert_eq!(node.value, 2); } assert_eq!(tree.right, None); } #[test] fn insert_right() { let tree = BinaryTree::new(1).right(BinaryTree::new(2)); if let Some(node) = tree.right { assert_eq!(node.value, 2); } assert_eq!(tree.left, None); } #[test] fn insert() { let mut tree = BinaryTree::new(1); tree.insert(2); tree.insert(3); tree.insert(4); tree.insert(5); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3)) ); tree.insert(6); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3).left(BinaryTree::new(6))) ) } #[test] fn create_new_tree_from() { let tree = BinaryTree::from(&[1, 2, 3, 4, 5, 6]); assert_eq!( tree, BinaryTree::new(1) .left( BinaryTree::new(2) .left(BinaryTree::new(4)) .right(BinaryTree::new(5)) ) .right(BinaryTree::new(3).left(BinaryTree::new(6))) ) } }