Implementing a B-Tree Map in Rust

B-Tree Maps are a powerful data structure offering efficient sorted key-value storage and retrieval. This challenge asks you to implement a simplified version of a B-Tree Map in Rust, focusing on core functionality like insertion, deletion, and searching. Successfully completing this challenge will deepen your understanding of tree-based data structures and their practical applications.

Problem Description

You are tasked with implementing a BTreeMap in Rust. This BTreeMap should support the following operations:

• insert(key: K, value: V): Inserts a key-value pair into the map, maintaining sorted order based on the key.
• get(key: &K): Retrieves the value associated with a given key. Returns None if the key is not found.
• remove(key: &K): Removes the key-value pair associated with the given key. Returns Some(V) if the key was found and removed, and None otherwise.
• len(): Returns the number of key-value pairs in the map.
• is_empty(): Returns true if the map is empty, false otherwise.

For simplicity, assume that the keys are Orderable and the values are Clone. You do not need to implement iteration or other advanced features. Focus on the core tree structure and operations.

Key Requirements:

• The implementation should maintain the sorted order of keys.
• The tree should be balanced to ensure efficient operations (though perfect balancing is not strictly required, strive for reasonable balance).
• Handle duplicate keys by overwriting the existing value (like the standard BTreeMap).
• Handle empty trees gracefully.

Expected Behavior:

The BTreeMap should behave similarly to the standard BTreeMap in terms of insertion, retrieval, and deletion, but with a simplified implementation. The operations should be efficient, with a time complexity of O(log n) for insertion, deletion, and retrieval, where n is the number of elements in the tree.

Edge Cases to Consider:

• Inserting duplicate keys.
• Removing a key that doesn't exist.
• Getting a key that doesn't exist.
• Inserting and removing elements from an empty tree.
• Handling very large trees (consider memory usage and potential stack overflow issues if recursion is not managed carefully).

Examples

Example 1:

Input:
insert(3, "apple");
insert(1, "banana");
insert(2, "cherry");
get(&1);
remove(&2);
get(&2);
len();

Output:

Some("banana")
None
0

Explanation: The tree is initially populated with (3, "apple"), (1, "banana"), and (2, "cherry"). get(&1) returns "banana". Removing (2, "cherry") leaves (3, "apple") and (1, "banana"). get(&2) returns None because the key is no longer present. len() returns 2.

Example 2:

Input:
insert(5, "grape");
insert(5, "kiwi"); // Overwrite existing value
get(&5);
remove(&5);
len();
is_empty();

Output:

Some("kiwi")
None
0
true

Explanation: Inserting (5, "grape") and then (5, "kiwi") overwrites the value associated with key 5. get(&5) returns "kiwi". Removing (5, "kiwi") leaves the tree empty. len() returns 0, and is_empty() returns true.

Example 3: (Edge Case - Empty Tree)

Input:
len();
is_empty();
insert(10, "orange");
get(&10);
remove(&10);
len();
is_empty();

Output:

0
true
Some("orange")
None
0
true

Explanation: The tree starts empty. len() returns 0 and is_empty() returns true. Inserting (10, "orange") adds a single element. get(&10) returns "orange". Removing (10, "orange") empties the tree again. len() returns 0 and is_empty() returns true.

Constraints

• The number of elements in the BTreeMap will not exceed 1000.
• Keys must implement the Ord trait.
• Values must implement the Clone trait.
• The implementation should strive for O(log n) time complexity for insertion, deletion, and retrieval. While perfect balancing isn't required, avoid degenerate tree structures (e.g., a linear chain).
• Memory usage should be reasonable.

Notes

• Consider using recursion to traverse and manipulate the tree.
• Think about how to handle node splitting and merging to maintain balance.
• You can choose the branching factor of your B-Tree (the maximum number of children a node can have). A branching factor of 3 is a common choice.
• Start with a basic implementation of insertion and retrieval, then add deletion and other methods.
• Thoroughly test your implementation with various inputs, including edge cases.
• Focus on clarity and readability of your code. Good comments are appreciated.