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

Check out 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

About Author

COMENTARIOS

ETIQUETAS

ESTE ARTÍCULO FUE PRESENTADO EN

Related Stories

Una guía del arquitecto para crear una arquitectura de referencia para un lago de datos de IA/ML

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Una guía del arquitecto para crear una arquitectura de referencia para un lago de datos de IA/ML

Creación de productos criptográficos centrados en el usuario: la importancia de los comentarios de los clientes

Aumente su productividad con estas 18 herramientas para desarrolladores 🚀🔥

¿Quieres ganar un concurso de redacción de HackerNoon? Esto es lo que recomiendan los ganadores del concurso #crypto-api

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps