Chapters 4-10: Assignement

[radumarias]

Please see The Rust Book and follow the steps from For students to create and submit your solutions.

Chapters 4-10 #6

Please create the code needed for this and submit it as above.

Create a B-tree like structure, with each node having fields like:

Node<T>:
    id: u64, // can be a sequence 
    val: <T>,
    left: Vec<Node>, // sorted ascending
    right: Vec<Node>, // sorted ascending

and an enum Direction with variants: Left, Right

Starting from a root element, each node stores in the left list nodes with a value smaller than the node val and in the right list nodes with values equal to or bigger than the node val.

Node having methods like:

add(val: T) -> u64 // adds a node and returns the id
remove_by_id(id: T) -> Result<(), io::Error> // removes the child node by id, not recursively
remove_by_val(val: T) -> Result<(), io::Error> // removes all children nodes with this value, not recursively
get_by_id(id: u64) -> Option<&Node>
get_by_id_mut(id: u64) -> Option<&mut Node>
get_by_val(val: T) -> Option<&[Node]>
get_by_val_mut(val: T) -> Option<&mut [Node]>
get_children(direction: Direction) -> &[Node]
get_children_mut(direction: Direction) -> &mut [Node]
print(direction: Direction) // print recursively the node value and all children values first going in the specified `direction`.

Balancing

When adding/removing nodes make sure the tree remains balanced as defined in B-tree in Definition section.

Manual

For simplicity you could manually balance the tree when adding elements, like using get_by_id_mut or get_children_mut and manually adding/removing children and also ordering the left and right.

Automatic

If you have time you can try to implement also auto balancing.