SplayTreeMap : A self-balancing binary search tree-based map in Dart

SplayTreeMap is a self-balancing binary search tree-based map that maintains its keys in sorted order. It is part of Dart’s dart:collection library and provides efficient operations for searching, inserting, and deleting elements.

---

📌 Key Features of SplayTreeMap

1. Sorted Keys

   • Unlike a normal Map, SplayTreeMap keeps its keys sorted in ascending order.

2. Self-Balancing

   • Uses splaying (a tree rotation technique) to keep recently accessed elements closer to the root, improving access time for frequently used elements.

3. Faster Lookup for Recent Elements

   • Frequently accessed elements are moved closer to the root, making their lookup faster.

4. Efficient Operations

   • Search, Insert, and Delete operations all take O(log n) time on average.

---

🛠 How to Use SplayTreeMap

✅ Basic Example

import 'dart:collection';

void main() {
  SplayTreeMap<int, String> treeMap = SplayTreeMap();

  // Adding elements
  treeMap[3] = "Three";
  treeMap[1] = "One";
  treeMap[2] = "Two";
  treeMap[5] = "Five";

  // Keys are automatically sorted
  print(treeMap); // {1: One, 2: Two, 3: Three, 5: Five}

  // Getting the first and last key
  print("First Key: ${treeMap.firstKey()}"); // 1
  print("Last Key: ${treeMap.lastKey()}");   // 5

  // Removing an element
  treeMap.remove(2);
  print(treeMap); // {1: One, 3: Three, 5: Five}

  // Iterating over the sorted map
  for (var entry in treeMap.entries) {
    print("${entry.key}: ${entry.value}");
  }
}

---

🔥 Key Methods

Method	Description
firstKey()	Returns the smallest key in the map.
lastKey()	Returns the largest key in the map.
remove(key)	Removes an entry by key.
containsKey(key)	Checks if a key exists.
containsValue(value)	Checks if a value exists.
clear()	Removes all entries.
length	Returns the number of entries.

---

🔄 Use Case: Storing Sorted Data Efficiently

📌 Example: Keeping Users Sorted by Age

import 'dart:collection';

void main() {
  var users = SplayTreeMap<int, String>();

  users[25] = "Alice";
  users[30] = "Bob";
  users[22] = "Charlie";
  users[28] = "David";

  print(users); // {22: Charlie, 25: Alice, 28: David, 30: Bob}
}

👉 The keys (ages) remain sorted automatically!

---

🤔 When to Use SplayTreeMap?

✅ Use SplayTreeMap when:

• You need sorted keys automatically.
• You perform frequent lookups on recently accessed elements (it optimizes for repeated access patterns).

❌ Avoid if:

• You don’t need sorted keys (a HashMap is faster for general lookup operations).

---

📌 Built-in Methods of SplayTreeMap in Dart

Some important methods for sorting, searching, inserting, and manipulating a SplayTreeMap.

---

🏷 Sorting Methods

Method	Description
firstKey()	Returns the smallest key.
lastKey()	Returns the largest key.
firstEntry()	Returns the first key-value pair.
lastEntry()	Returns the last key-value pair.

Example:

import 'dart:collection';

void main() {
  var treeMap = SplayTreeMap<int, String>();
  treeMap[5] = "Five";
  treeMap[2] = "Two";
  treeMap[8] = "Eight";
  treeMap[1] = "One";

  print(treeMap.firstKey());   // 1
  print(treeMap.lastKey());    // 8
  print(treeMap.firstEntry()); // MapEntry(1: One)
  print(treeMap.lastEntry());  // MapEntry(8: Eight)
}

---

🔍 Search Methods

Method	Description
containsKey(key)	Returns true if the key exists.
containsValue(value)	Returns true if the value exists.
lookup(key)	Returns the value associated with the key (or null if not found).

Example:

import 'dart:collection';

void main() {
  var treeMap = SplayTreeMap<int, String>();
  treeMap[10] = "Ten";
  treeMap[20] = "Twenty";
  treeMap[30] = "Thirty";

  print(treeMap.containsKey(20));  // true
  print(treeMap.containsValue("Ten"));  // true
  print(treeMap.lookup(30));  // Thirty
}

---

✏ Insertion & Deletion Methods

Method	Description
putIfAbsent(key, () => value)	Adds a key-value pair only if the key doesn't exist.
update(key, (existing) => newValue, ifAbsent: () => newValue)	Updates a key's value or inserts it if missing.
remove(key)	Removes a key-value pair.
clear()	Removes all elements.

Example:

import 'dart:collection';

void main() {
  var treeMap = SplayTreeMap<int, String>();

  treeMap.putIfAbsent(5, () => "Five");
  treeMap.update(5, (existing) => "Updated Five", ifAbsent: () => "Five");
  
  print(treeMap);  // {5: Updated Five}

  treeMap.remove(5);
  print(treeMap);  // {}
}

---

🔄 Iteration Methods

Method	Description
forEach((key, value) => action)	Iterates over all entries.
entries	Returns all key-value pairs as MapEntry objects.
keys	Returns a list of all keys.
values	Returns a list of all values.

Example:

import 'dart:collection';

void main() {
  var treeMap = SplayTreeMap<int, String>();
  treeMap[3] = "Three";
  treeMap[1] = "One";
  treeMap[2] = "Two";

  treeMap.forEach((key, value) {
    print("$key: $value");
  });

  print(treeMap.keys.toList());  // [1, 2, 3]
  print(treeMap.values.toList());  // [One, Two, Three]
}

---

🏆 Advanced Methods

Method	Description
removeWhere((key, value) => condition)	Removes elements that satisfy a condition.
addAll({key1: value1, key2: value2})	Adds multiple key-value pairs.

Example:

import 'dart:collection';

void main() {
  var treeMap = SplayTreeMap<int, String>();
  treeMap.addAll({1: "One", 2: "Two", 3: "Three", 4: "Four"});

  treeMap.removeWhere((key, value) => key % 2 == 0);
  
  print(treeMap);  // {1: One, 3: Three}
}

---

🎯 When to Use SplayTreeMap?

✅ Use SplayTreeMap when:

• You need keys to be sorted automatically.
• You frequently access recently used keys.
• You require fast insertion, deletion, and lookup (O(log n)).

❌ Avoid if:

• You don’t need sorted keys (use HashMap instead for faster lookups).
• The dataset is small (List or Map might be simpler).

---

🎉 Conclusion

SplayTreeMap is a powerful and efficient way to store sorted key-value pairs. It provides various methods for sorting, searching, inserting, deleting, and iterating efficiently.🚀