js实现treemap
实现 TreeMap 的基本思路
TreeMap 是一种基于红黑树（Red-Black Tree）实现的有序键值对数据结构。在 JavaScript 中，可以通过对象或 Map 结合自定义排序逻辑来模拟 TreeMap 的功能。
使用 JavaScript 实现 TreeMap
方法一：基于数组和二分查找
通过数组存储键值对，并使用二分查找维护有序性。插入和删除操作需要手动维护数组的顺序。
class TreeMap {
constructor() {
this.keys = [];
this.values = [];
}
// 二分查找插入位置
_findIndex(key) {
let low = 0, high = this.keys.length;
while (low < high) {
const mid = Math.floor((low + high) / 2);
if (this.keys[mid] < key) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
set(key, value) {
const index = this._findIndex(key);
if (index < this.keys.length && this.keys[index] === key) {
this.values[index] = value; // 更新已有键
} else {
this.keys.splice(index, 0, key);
this.values.splice(index, 0, value); // 插入新键
}
}
get(key) {
const index = this._findIndex(key);
if (index < this.keys.length && this.keys[index] === key) {
return this.values[index];
}
return undefined;
}
delete(key) {
const index = this._findIndex(key);
if (index < this.keys.length && this.keys[index] === key) {
this.keys.splice(index, 1);
this.values.splice(index, 1);
return true;
}
return false;
}
has(key) {
const index = this._findIndex(key);
return index < this.keys.length && this.keys[index] === key;
}
}方法二：基于 JavaScript 的 Map 和排序
利用 Map 存储键值对，并在需要时对键进行排序。适用于不频繁插入但需要有序遍历的场景。
class TreeMap {
constructor() {
this.map = new Map();
}
set(key, value) {
this.map.set(key, value);
}
get(key) {
return this.map.get(key);
}
delete(key) {
return this.map.delete(key);
}
has(key) {
return this.map.has(key);
}
// 返回排序后的键值对数组
entries() {
return Array.from(this.map.entries()).sort((a, b) => a[0] - b[0]);
}
}性能优化建议
- 对于频繁插入和删除的场景，方法一的数组实现可能性能较差（O(n) 时间）。可以结合更高效的数据结构（如平衡二叉搜索树）优化。
- 如果需要高性能的 TreeMap，可以考虑使用第三方库（如
bintrees或immutable.js的OrderedMap）。
示例用法
const treeMap = new TreeMap();
treeMap.set(3, 'three');
treeMap.set(1, 'one');
treeMap.set(2, 'two');
console.log(treeMap.entries()); // [[1, 'one'], [2, 'two'], [3, 'three']]
console.log(treeMap.get(2)); // 'two'通过以上方法，可以在 JavaScript 中实现类似 Java TreeMap 的功能，支持有序键值对操作。
