JS如何实现替罪羊树？平衡因子的控制

class GoatNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.size = 1; // 子树大小，包括自身
  }
}

class GoatTree {
  constructor(alpha = 0.7) {
    this.root = null;
    this.size = 0;
    this.alpha = alpha; // 平衡因子，通常取0.5 < alpha < 1
  }

  // 更新节点大小
  updateSize(node) {
    if (node) {
      node.size = 1 + (node.left ? node.left.size : 0) + (node.right ? node.right.size : 0);
    }
  }

  // 插入节点
  insert(key, value) {
    const newNode = new GoatNode(key, value);
    if (!this.root) {
      this.root = newNode;
      this.size = 1;
      return;
    }

    let parent = null;
    let current = this.root;
    let culprit = null; // 替罪羊节点

    while (current) {
      parent = current;
      current.size++; // 沿途更新size
      if (key < current.key) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }

      // 检查是否失衡
      if (current.size > 1 && (current.left && current.left.size > this.alpha * current.size || current.right && current.right.size > this.alpha * current.size)) {
        culprit = current;
      }
    }

    this.size++;

    // 找到替罪羊，重构
    if (culprit) {
      this.rebuild(culprit);
    }
  }

  // 删除节点（懒删除，仅标记）
  delete(key) {
    // 简化版，实际应用中需要考虑懒删除或物理删除
    // 这里仅作为示例，不完整实现删除
    let node = this.search(key);
    if(node){
        // 找到节点，可以标记为已删除，或者直接物理删除并重构
        // 物理删除更复杂，需要考虑子节点
        this.size--;
    }
  }


  // 搜索节点
  search(key) {
    let current = this.root;
    while (current) {
      if (key === current.key) {
        return current;
      } else if (key < current.key) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return null;
  }

  // 中序遍历，用于拍扁树
  flatten(node, array = []) {
    if (!node) return array;
    this.flatten(node.left, array);
    array.push(node);
    this.flatten(node.right, array);
    return array;
  }

  // 从排序数组构建平衡树
  buildBalancedTree(array, start, end) {
    if (start > end) return null;
    const mid = Math.floor((start + end) / 2);
    const node = array[mid];
    node.left = this.buildBalancedTree(array, start, mid - 1);
    node.right = this.buildBalancedTree(array, mid + 1, end);
    this.updateSize(node); // 重要：更新节点大小
    return node;
  }


  // 重构子树
  rebuild(node) {
    const parent = this.findParent(node.key, this.root); // 找到替罪羊的父节点
    const flattened = this.flatten(node); // 拍扁子树
    const rebuiltSubtree = this.buildBalancedTree(flattened, 0, flattened.length - 1); // 重建平衡树

    if (!parent) {
      this.root = rebuiltSubtree; // 如果替罪羊是根节点
    } else if (node.key < parent.key) {
      parent.left = rebuiltSubtree;
    } else {
      parent.right = rebuiltSubtree;
    }

    this.updateSize(parent); // 更新父节点的大小

  }


  // 找到节点的父节点
  findParent(key, node, parent = null) {
    if (!node) return null;
    if (node.key === key) return parent;

    if (key < node.key) {
      return this.findParent(key, node.left, node);
    } else {
      return this.findParent(key, node.right, node);
    }
  }
}

alpha

alpha

alpha

0.5 < alpha < 1

0.7

alpha