当前位置：首页 > JavaScript

js实现treemap

2026-04-06 15:45:20JavaScript

实现 TreeMap 的基本思路

TreeMap 是一种基于红黑树实现的有序映射结构，JavaScript 本身不提供原生 TreeMap，但可以通过对象或 Map 结合自定义排序逻辑模拟。

使用对象实现简单 TreeMap

通过对象存储键值对，并维护一个排序数组来保证键的顺序：

class TreeMap {
  constructor() {
    this.items = {};
    this.sortedKeys = [];
  }

  set(key, value) {
    if (!(key in this.items)) {
      const index = this._findInsertIndex(key);
      this.sortedKeys.splice(index, 0, key);
    }
    this.items[key] = value;
  }

  get(key) {
    return this.items[key];
  }

  _findInsertIndex(key) {
    let low = 0;
    let high = this.sortedKeys.length;

    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (this.sortedKeys[mid] < key) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}

基于数组实现完整功能

更完整的实现包括遍历、删除等操作：

class AdvancedTreeMap {
  constructor(comparator = (a, b) => a - b) {
    this.keys = [];
    this.values = [];
    this.comparator = comparator;
  }

  set(key, value) {
    const index = this._findIndex(key);
    if (index < this.keys.length && this.comparator(this.keys[index], key) === 0) {
      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.comparator(this.keys[index], key) === 0) {
      return this.values[index];
    }
    return undefined;
  }

  _findIndex(key) {
    let low = 0;
    let high = this.keys.length;
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (this.comparator(this.keys[mid], key) < 0) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}

使用 ECMAScript 6 的 Map

对于需要更复杂功能的场景，可以扩展 ES6 的 Map 类：

class TreeMap extends Map {
  constructor(iterable, comparator = (a, b) => a - b) {
    super();
    this.comparator = comparator;
    this._keys = [];
    if (iterable) {
      for (const [key, value] of iterable) {
        this.set(key, value);
      }
    }
  }

  set(key, value) {
    if (!this.has(key)) {
      const index = this._findIndex(key);
      this._keys.splice(index, 0, key);
    }
    super.set(key, value);
    return this;
  }

  _findIndex(key) {
    let low = 0;
    let high = this._keys.length;
    while (low < high) {
      const mid = Math.floor((low + high) / 2);
      if (this.comparator(this._keys[mid], key) < 0) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
}