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 la estructura de datos se ve así: Árbol binario Cada nodo no tiene más de dos nodos secundarios. Nos referimos a ellos como niño y niño . Podemos traducir la descripción a código Rust así: left right pub struct BinaryTree<T> { pub value: T, pub left: Option<Box<BinaryTree<T>>>, pub right: Option<Box<BinaryTree<T>>>, } La estructura contiene un valor con el tipo genérico . Usamos enum para representar que el hijo y son opcionales. BinaryTree T Option left right Una es que contiene un valor del tipo o que representa que no lo contiene. Debido a que estamos usando para expresar si un valor es algo o nada, el compilador de Rust puede verificar si manejamos todos los casos. . En comparación con JavaScript, donde usamos un valor para expresar el mismo concepto, me anima a manejar los casos de uso por adelantado y me ahorra muchos problemas en el tiempo de ejecución. Option<T> Some T None Option para prevenir errores null Option The es uno de los punteros inteligentes. Guarda una dirección que apunta a datos en la memoria. nos ayuda a crear una estructura 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. Box Box BinaryTree es una de las razones por las que Rust es tan eficaz e interesante de aprender. Gestión de la memoria 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 toma el valor de y devuelve un que contiene el valor y ningún nodo secundario. new función asociada T BinaryTree Ahora que podemos usar 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 BinaryTree::new(1) .left(BinaryTree::new(2)) .right(BinaryTree::new(3)) Por suerte, encontré un de mi amigo en trivago, , explicando exactamente cómo implementarlo. Excelente artículo Matías 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 sin ningún otro requisito, ¿puedo insertar un nodo y el árbol encuentra el siguiente lugar disponible para mí? árbol binario equilibrado 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 fashion e insertando un nodo tan pronto como encontremos un nodo hijo ausente. primero en anchura La forma más fácil de implementar un recorrido de respiración primero es con un . Rust tiene un en la biblioteca estándar que podemos usar. Cola VecDequeue 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 o está ausente. Si encontramos uno, ese es el próximo lugar disponible para el nuevo nodo. left right Es un algoritmo bastante sencillo, pero . el problema era que no entendía . Luché para hacerlo bien propiedad en Rust Repasemos juntos el método de . insert Lo primero que queremos decidir es cómo queremos usar el primer argumento . se refiere a la instancia de a la que se llama el método. Lo que necesitamos de nosotros es poder mutar el nodo secundario y para que podamos insertar un nuevo nodo. Simplemente pasar una referencia mutable hará el trabajo porque el método no necesita tomar posesión de . self self BinaryTree self left right &mut self self Para el tipo de datos del elemento , podemos usar el mismo tipo de datos que para almacenar referencias mutables de . VecDeque self BinaryTree Al hacer estallar la cola dentro del ciclo, queremos usar una referencia mutable a y porque queremos insertar el nuevo nodo. left right Al insertar el nuevo nodo, la y la para permitir la asignación de nuevos nodos, así: . desreferencia left right *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 a la estructura . PartialEq 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 , podemos considerar crear un árbol equilibrado de manera más conveniente. Por ejemplo, quiero tener algo similar a : una función asociada que toma una matriz y devuelve un equilibrado. insert Vec::from BinaryTree::from BinaryTree 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 , podemos iterar a través de la matriz y usar el método de para crear la estructura de árbol. BinaryTree::from insert 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 implementa el rasgo . T Copy - impl<T> BinaryTree<T> { + impl<T> BinaryTree<T> + where + T: Copy, + { La razón es que el método de en realidad toma posesión de . Para mantener la memoria del programa guardada, el compilador no nos permitió "mover" los elementos del arreglo al método de 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. insert new_value insert ¡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))) ) } } Referencia Árbol binario Árbol binario equilibrado Búsqueda primero en amplitud Cola Tipo Óxido Option Puntero de Óxido Box Óxido VecDequeue Rasgo Óxido PartialEq rasgo Óxido Copy Óxido Vec::from Función asociada a óxido propiedad de óxido JavaSCript null La pila y el montón Of Boxes and Trees - Punteros inteligentes en Rust Problema con la implementación de la inserción de árboles binarios La enumeración de opciones y sus ventajas sobre los valores nulos Tratar los punteros inteligentes como referencias regulares con el rasgo Deref Este artículo se publicó originalmente en . el sitio web de Daw-Chih

Mozilla

Super

Twitter

2022 - HackerNoon Contributor of the Year - Leadership

2022 - HackerNoon Contributor of the Year - Learning

2022 - HackerNoon Contributor of the Year - Product Management

2022 - HackerNoon Contributor of the Year - Software Engineering

2022 - HackerNoon Contributor of the Year - Typescript

Coding Guru of 2022

Checkout my website!

Nominated for 2022 - HackerNoon Contributor of the Year - Product Management

Nominated for 2022 - HackerNoon Contributor of the Year - Typescript

Nominated for 2022 - HackerNoon Contributor of the Year - Leadership

Nominated for 2022 - HackerNoon Contributor of the Year - Software Engineering

Nominated for Coding Guru of 2022

Nominated for 2022 - HackerNoon Contributor of the Year - Learning

Este audio es producido en el idioma original de la historia!

Demasiado Largo; Para Leer

Cómo insertar un árbol binario en Rust

Cómo insertar un árbol binario en Rust

Demasiado Largo; Para Leer

Companies Mentioned

@dawchihliou

HISTORIAS RELACIONADAS