Index

Rust

  1. Guessing Game
  2. Common Programming Concepts
    1. Variables and Mutability
    2. Data Types
    3. Function
    4. Control Flow
  3. Understanding Ownership
    1. References and Borrowing
    2. The Slice Type
  4. Using Structs
    1. An Example Program Using Structs
    2. Method Syntax
  5. Enums and Pattern Matching
    1. The match Control Flow Operator
    2. Concise Control Flow with if let
  6. Managing Growing Projects with Packages, Crates, and Modules
    1. Defining Modules to Control Scope and Privacy
    2. Paths for Referring to an Item in the Module Tree
    3. Bringing Paths into Scope with the use Keyword
    4. Separating Modules into Different Files
  7. Common Collections
    1. Storing UTF-8 Encoded Text with Strings
    2. Storing Keys with Associated Values in Hash Maps
  8. Error Handling
    1. Unrecoverable Errors with panic!
    2. Recoverable Errors with Result
  9. Generic Types, Traits, and Lifetimes
    1. Traits: Defining Shared Behavior
    2. Generics Rust by Example
      1. Functions
      2. Implementation
  10. Writing Automated Tests
  11. Object Oriented Programming
  12. Adding dependancies
  13. Option Take
  14. RefCell
  15. mem
  16. Data Structure
    1. Linked List
    2. Binary search tree
    3. N-ary Sum tree
  17. Recipe
    1. Semi colon
    2. Calling rust from python
    3. Default
    4. Crytocurrency With rust
    5. Function chaining
    6. Question Mark Operator
    7. Tests with println
    8. lib and bin
    9. Append vector to hash map
    10. Random Number
    11. uuid4
    12. uwrap and option
  18. Blockchain with Rust
  19. Near Protocol
    1. Startup code
    2. Couter
    3. Status
    4. Avrit
  20. Actix-web

Binary search tree


Code:
https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Rust/blob/master/Chapter05/src/binary_search_tree.rs

Data structures: Binary Search Tree
https://www.youtube.com/watch?v=pYT9F8_LFTM

images/946-1.png


images/946-2.png


A tree structure is almost like a linked list: each node has branches—in the case of a binary tree, there are two—which represent children of that node. Since these children have children of their own, the node count grows exponentially, building a hierarchical structure that looks like a regular tree turned on its head.

Binary trees are a subset of these structures with only two branches, typically called left and right.


However, that does not inherently help the tree's performance. This is why using a binary search tree, where left represents the smaller or equal value to its parent, and right anything that's greater than that parent node, was established!


If that was confusing, don't worry; there will be code. First, some vocabulary though: what would you call the far ends of the tree? Leaves. Cutting off branches? Pruning. The number of branches per node? Branching factor (binary trees have a branching factor of 2)

fn main() {
    type Tree = Option<Box<Node>>;

    struct Node {
        pub value: u64,
        left: Tree,
        right: Tree,
    }
    // 1. Tree structure itself is only a pointer to the root node
    pub struct BinarySearchTree {
        root: Tree,
        pub length: u64,
    }
}


Store IoT device objects (containing the IP address, numerical name, and type)
Retrieve IoT objects by numerical name
Iterate over IoT objects

A great use for a tree: the numerical name can be used to create a tree and search for it nice and quickly.

#[derive(Clone, Debug)]
pub struct IoTDevice {
    pub numerical_id: u64,
    pub address: String,
}


For simplicity, this object will be used in the code directly (adding generics isn't too tricky, but would go beyond the scope of this book):

type Tree = Option<Box<Node>>;
struct Node {
    pub dev: IoTDevice,
    left: Tree,
    right: Tree,
}


Starting with this basic implementation, the requisite operations, add and find, can be implemented.

More devices



Unlike lists, trees make a major decision on insert: which side does the new element go to? Starting at the root node, each node's value is compared to the value that is going to be inserted: is this greater than or less than that? Either decision will lead down a different subtree (left or right).

This process is (usually recursively) repeated until the targeted subtree is None, which is exactly where the new value is inserted—as a leaf of the tree. If this is the first value going into the tree, it becomes the root node. There are some problems with this, and the more experienced programmers will have had a strange feeling already: what happens if you insert numbers in ascending order?


These feelings are justified. Inserting in ascending order (for example, 1, 2, 3, 4) will lead to a tree that is basically a list in disguise! This is also called a (very) unbalanced tree and won't have any of the benefits of other trees:

1
/ \
2
/ \
3
/ \
4

During this chapter, we are going to go a lot more things on balancing trees and why that is important in order to achieve high performance. In order to avoid this pitfall associated with binary search trees, the first value to insert should ideally be the median of all elements since it will be used as the root node, as is visible in the following code snippet:


Insert some record:

https://youtu.be/pYT9F8_LFTM?t=1065


images/946-3.png

Remember we can also reverse it turning left to right, and the algorithm will not change.



use std::mem;
fn main() {
    type Tree = Option<Box<Node>>;

    #[derive(Clone, Debug)]
    pub struct IoTDevice {
        pub numerical_id: u64,
        pub address: String,
    }

    impl IoTDevice {
        pub fn new(id: u64, address: String) -> IoTDevice {
            IoTDevice {
                address: address,
                numerical_id: id,
            }
        }
    }
    
    #[derive(Debug)]
    struct Node {
        pub dev: IoTDevice,
        left: Tree,
        right: Tree,
    }

    impl Node {
        pub fn new(dev: IoTDevice) -> Tree {
            Some(Box::new(Node {
                dev: dev,
                left: None,
                right: None,
            }))
        }
    }
    // 1. Tree structure itself is only a pointer to the root node
    pub struct DeviceRegistry {
        root: Tree,
        pub length: u64,
    }

    impl DeviceRegistry {
        pub fn new_empty() -> DeviceRegistry {
            DeviceRegistry {
                root: None,
                length: 0,
            }
        }
        pub fn add(&mut self, device: IoTDevice) {
            self.length += 1;
            // 2. `self.root` value is given to root, and `self.root` now contains `None`
            let root = mem::replace(&mut self.root, None);
            self.root = self.add_rec(root, device);
            // println!("{:?}", self.root);
        }

        fn add_rec(&mut self, node: Tree, device: IoTDevice) -> Tree {
            match node {
                Some(mut n) => {
                    if n.dev.numerical_id <= device.numerical_id {
                        n.left = self.add_rec(n.left, device); //recursion
                        println!("Left");
                        
                        Some(n)
                    } else {
                        n.right = self.add_rec(n.right, device);
                        println!("Right");
                        Some(n)
                    }
                }
                _ => {
                    println!("Null node");
                    Node::new(device)
                },
            }
        }
    }

    fn new_device_with_id(id: u64, address: String) -> IoTDevice {
        IoTDevice::new(id, address)
    }

    let mut bst = DeviceRegistry::new_empty();
    bst.add(new_device_with_id(15, "Fifteen device".to_owned()));
    bst.add(new_device_with_id(10, "Ten device".to_owned()));
    bst.add(new_device_with_id(20, "Twenty device".to_owned()));
    bst.add(new_device_with_id(8, "Eight device".to_owned()));
    bst.add(new_device_with_id(12, "Twelve device".to_owned()));
    bst.add(new_device_with_id(17, "Seventeen device".to_owned()));
    bst.add(new_device_with_id(25, "Twenty Five device".to_owned()));
}


Paste the code in the first line of text editor to get the line number.


images/946-4.png




Some(Node { dev: IoTDevice { numerical_id: 15, address: "Fifteen device" }, 
    left: 
        Some(Node { dev: IoTDevice { numerical_id: 20, address: "Twenty device" }, 
            left: 
                Some(Node { dev: IoTDevice { numerical_id: 25, address: "Twenty Five device" }, 
                    left: None, 
                    right: None }), 
            right: 
                Some(Node { dev: IoTDevice { numerical_id: 17, address: "Seventeen device" }, 
                    left: None, 
                    right: None }) }), 
    right: 
        Some(Node { dev: IoTDevice { numerical_id: 10, address: "Ten device" }, 
            left: 
                Some(Node { dev: IoTDevice { numerical_id: 12, address: "Twelve device" }, 
                    left: None, 
                    right: None }), 
            right: Some(Node { dev: IoTDevice { numerical_id: 8, address: "Eight device" }, 
                    left: None, 
                    right: None }) }) })