TreeMaps / SortedDicts

"""
A TreeMap is a self-balancing binary search tree. In modern languages, this is normally implemented as a Red-black tree.

TreeMap comes in handy when you need:
1. fast random access by key
2. maintaining order of the key, as well as
3. updating the key order quickly

If the requirements are only 1) and 2), we can get away with a hashmap and a list/array and that's exactly what most interview problems ask.

Python does not have a built-in TreeMap data structure as found in some other languages like Java. However, you can achieve similar functionality using the sortedcontainers module, specifically the SortedDict class. This module provides efficient implementations of sorted collections, including sorted dictionaries which can function similarly to a TreeMap.

A SortedDict is different from collections.OrderedDict in that a SortedDict maintains the keys in sorted order, while an OrderedDict maintains the keys in the order in which they were inserted (similar to a list that is repeatedly appended to).
"""
from sortedcontainers import SortedDict

# Creating a SortedDict
tree_map = SortedDict()

# Adding elements
tree_map['b'] = 2
tree_map['a'] = 1
tree_map['c'] = 3

# Accessing elements
print(tree_map['a'])  # Output: 1
print(tree_map['b'])  # Output: 2
print(tree_map['c'])  # Output: 3

# Checking for existence of keys
print('a' in tree_map)  # Output: True
print('d' in tree_map)  # Output: False

# Removing elements
del tree_map['b']

# Iterating through the SortedDict
for key in tree_map:
    print(f"{key}: {tree_map[key]}")  # Output: a: 1, c: 3

# Getting all keys and values
keys = tree_map.keys()
values = tree_map.values()
items = tree_map.items()

print("Keys:", list(keys))       # Output: ['a', 'c']
print("Values:", list(values))   # Output: [1, 3]
print("Items:", list(items))     # Output: [('a', 1), ('c', 3)]

# Finding the smallest and largest keys
smallest_key = tree_map.peekitem(0)[0]  # Get the first item (smallest key)
largest_key = tree_map.peekitem(-1)[0]  # Get the last item (largest key)

print("Smallest key:", smallest_key)  # Output: a
print("Largest key:", largest_key)    # Output: c

# Finding the closest key greater than or equal to a given key
key = tree_map.bisect_left('b')
if key < len(tree_map):
    print("Closest key >= 'b':", tree_map.peekitem(key)[0])  # Output: c

# Example usage
print("TreeMap after all operations:", tree_map)  # Output: SortedDict({'a': 1, 'c': 3})