Dart SplayTreeNode
last modified April 4, 2025
In Dart, SplayTreeNode is a node in a splay tree, a self-balancing binary search tree. It provides amortized O(log n) performance for operations.
Splay trees automatically move frequently accessed elements closer to the root. This makes them efficient for scenarios with temporal locality of reference.
Basic SplayTreeNode Structure
A SplayTreeNode contains a value and references to left and right children. It also maintains parent references for splaying operations.
import 'dart:collection';
void main() {
var root = SplayTreeNode<int>(50);
root.left = SplayTreeNode<int>(30);
root.right = SplayTreeNode<int>(70);
print('Root: ${root.value}');
print('Left child: ${root.left?.value}');
print('Right child: ${root.right?.value}');
}
We create a simple splay tree with root value 50. The left child is 30 and right child is 70. The tree structure is maintained through these references.
$ dart main.dart Root: 50 Left child: 30 Right child: 70
Inserting Nodes into Splay Tree
Inserting nodes into a splay tree automatically performs splaying operations. This brings the newly inserted node to the root position.
import 'dart:collection';
void main() {
var tree = SplayTreeSet<int>();
tree.addAll([50, 30, 70, 20, 40, 60, 80]);
print('Tree after insertion: $tree');
print('Root after insertion: ${tree.first}');
}
We use SplayTreeSet which internally uses SplayTreeNode. The addAll method inserts multiple values. The last inserted value becomes the new root.
$ dart main.dart
Tree after insertion: {20, 30, 40, 50, 60, 70, 80}
Root after insertion: 20
Searching in Splay Tree
Search operations in splay trees also trigger splaying. The searched node moves to the root position for faster future access.
import 'dart:collection';
void main() {
var tree = SplayTreeSet<int>.from([50, 30, 70, 20, 40, 60, 80]);
print('Before search, root: ${tree.first}');
bool found = tree.contains(60);
print('After search, root: ${tree.first}');
print('Element found: $found');
}
We create a splay tree and search for value 60. The contains method triggers splaying, bringing 60 to the root position for faster future access.
$ dart main.dart Before search, root: 20 After search, root: 60 Element found: true
Removing Nodes from Splay Tree
Removal operations in splay trees also perform splaying. The parent of the removed node becomes the new root.
import 'dart:collection';
void main() {
var tree = SplayTreeSet<int>.from([50, 30, 70, 20, 40, 60, 80]);
print('Before removal, root: ${tree.first}');
tree.remove(50);
print('After removal, root: ${tree.first}');
print('Tree after removal: $tree');
}
We remove the value 50 from the splay tree. The removal operation triggers splaying, bringing a nearby node to the root position for balance.
$ dart main.dart
Before removal, root: 20
After removal, root: 40
Tree after removal: {20, 30, 40, 60, 70, 80}
Custom Comparison in SplayTree
SplayTreeSet allows custom comparison functions. This enables sorting by different criteria than natural ordering.
import 'dart:collection';
void main() {
var tree = SplayTreeSet<String>(
(a, b) => a.length.compareTo(b.length)
);
tree.addAll(['apple', 'banana', 'kiwi', 'orange']);
print('Tree sorted by length: $tree');
print('Shortest word: ${tree.first}');
print('Longest word: ${tree.last}');
}
We create a splay tree that sorts strings by length rather than lexicographically. The comparison function determines the ordering of nodes in the tree.
$ dart main.dart
Tree sorted by length: {kiwi, apple, banana, orange}
Shortest word: kiwi
Longest word: orange
Best Practices
- Access Patterns: Use splay trees when access is non-uniform.
- Memory Usage: Be aware of higher memory overhead than arrays.
- Custom Ordering: Define comparison functions carefully.
- Thread Safety: Splay trees are not thread-safe by default.
Source
Dart SplayTreeSet Documentation
This tutorial covered Dart's SplayTreeNode and SplayTreeSet with practical examples demonstrating their key features and usage patterns.
Author
List all Dart tutorials.