{"id":351,"date":"2024-03-16T17:05:00","date_gmt":"2024-03-16T16:05:00","guid":{"rendered":"https:\/\/noiseonthenet.space\/noise\/?p=351"},"modified":"2024-03-17T18:03:43","modified_gmt":"2024-03-17T17:03:43","slug":"growing-a-binary-tree-in-rust","status":"publish","type":"post","link":"https:\/\/noiseonthenet.space\/noise\/2024\/03\/growing-a-binary-tree-in-rust\/","title":{"rendered":"Growing A (Binary) Tree in Rust"},"content":{"rendered":"

\"toa-heftiba-W1yjvf5idqA-unsplash_reduced.jpg\" <\/p> <\/div>\n\n

Photo by Toa Heftiba<\/a> on Unsplash<\/a> <\/p>\n\n

The code for this post is here<\/a> <\/p>\n

\n

What is a binary tree<\/h2>\n
\n

A tree is a data structure, familiar to most developers; it is composed at least of a “root” node which is its entry point. Each node can have one or many or no “chidren” nodes, so this is a kind of graph. Unlike other graphs however, “children” nodes in trees won’t have their “parents” as chidrens, nor any “ancestor”. In other words this graph has no circular paths, which creates a “hierarchical” structure. <\/p>\n\n

\"post011_rust_tree.png\" <\/p> <\/div>\n\n

If we draw this data structure with the root node in the bottom and chidren nodes above it looks like a plant, hence its name. We are going to grow a specific species of tree which has at maximum two “children” per each node: it is called “binary tree”. <\/p>\n\n

Those nodes who don’t have any childred are called “leaves” while those who have are called “branches”. <\/p>\n\n

Binary trees are used in machine learning models or to sort data etc. <\/p>\n<\/div>\n<\/div>\n

\n

A naive example from C<\/h2>\n
\n

Those who programmed in languages in the C family know that to define a tree each data structure representing a node should “connect” to similar structures; this is why we call them “recursive” data structures. <\/p>\n\n

To avoid infinite “loops” C uses “pointers” to connect a parent node with its childrens, so a first attempt to create this structures in rust can be using references <\/p>\n\n

\n