BTree的一种简单实现

最近在学习和理解红黑树的过程中，发现想要深入理解红黑树的本质离不开一种重要的数据结构，这种数据结构就是平衡树(BTree)，今天开始学习BTree的一些基本操作。

require("@fatso83/mini-mocha").install();
const { expect } = require('chai');
class BTreeNode {
  constructor(isLeaf){
    //是否属于叶子节点
    this.isLeaf = isLeaf;
    //节点用于存储具体数据的数组，且数据从前到后有顺序
    this.values = [];
    //存储节点对应的分支，或者子节点
    this.children = [];
    //存储节点所在的树节点
    this.tree = null;
    //节点对应的父节点
    this.parent = null;
  }

  /**
   * 获取节点存储数据的长度
   */
  get n() {
    return this.values.length;
  }

  /**
   * 在某个节点增加一个值
   */
  addValue(value) {
    if(!value) {
      return;
    }
    let pos = 0;
    while(pos < this.n && this.values[pos] < value) {
      pos++;
    }
    return this.values.splice(pos,0,value);
  }
  removeValue(pos) {
    if (pos >= this.n) {
      return null;
    }
    return this.values.splice(pos, 1)[0];
  }
  
  /**
   * 在指定位置添加一个子节点
   */
  addChild(node, pos) {
    this.children.splice(pos,0,node);
    node.parent = this;
  }

  /**
   * 删除指定位置的节点
   */
  removeChild(pos) {
    return this.children.splice(pos,1)[0];
  }
}

describe('BTreeNode test',()=>{
  it('BTreeNode init test',()=>{
    let bTreeNode = new BTreeNode(false);
    expect(bTreeNode.isLeaf).to.equal(false);
    expect(bTreeNode.n).to.equal(0);
    expect(bTreeNode.children.length).to.equal(0);
    expect(bTreeNode.tree).to.equal(null);
    expect(bTreeNode.parent).to.equal(null);
  });

  it('BTreeNode addValue test',()=>{
    let bTreeNode = new BTreeNode(false);
    bTreeNode.addValue(5);
    bTreeNode.addValue(8);
    bTreeNode.addValue(2);
    expect(bTreeNode.n).to.equal(3);
    const values = bTreeNode.values;
    expect(values.join('')).to.equal('258')
  });

  it('BTreeNode removeValue test',()=>{
    let bTreeNode = new BTreeNode(false);
    bTreeNode.addValue(3);
    bTreeNode.addValue(9);
    bTreeNode.addValue(7);
    bTreeNode.addValue(6);
    expect(bTreeNode.n).to.equal(4);
    const values = bTreeNode.values;
    expect(values.join('')).to.equal('3679');
    bTreeNode.removeValue(2);
    expect(bTreeNode.n).to.equal(3);
    const values1 = bTreeNode.values;
    expect(values1.join('')).to.equal('369');
  })
  
});

class BTree {
  constructor(order){
    this.order = order;
    this.root = null;
  }

  /**
   * Search a value in the Tree and return the node. O(log N)
   * @param {number} value 
   * @returns {BTreeNode}
   */
  searchValue(node,value) {
    if (node.values.includes(value)) {
      return node;
    }
    if (node.leaf) {
      return null;
    }
    let child = 0;
    while(child <= node.n && node.values[child]< parseInt(value,10)) {
      child++;
    }
    return this.searchValue(node.children[child],value);
  }

  /**
   * Insert a new value in the tree O(log N)
   * @param {number} value
   */
  insert(value) {
    const actual = this.root;
    if (actual.n === 2 * this.order - 1) {
      // Create a new node to become the root
      // Append the old root to the new one
      const temp = new BTreeNode(false);
      temp.tree = this;
      this.root = temp;
      temp.addChild(actual, 0);
      this.split(actual, temp, 1);
      this.insertNonFull(temp, parseInt(value));
    } else {
      this.insertNonFull(actual, parseInt(value));
    }
  }

  /**
   * Insert a value in a not-full node. O(1)
   * @param {BTreeNode} node 
   * @param {number} value
   */
  insertNonFull(node, value) {
    if (node.leaf) {
      node.addValue(value);
      return;
    }
    let temp = node.n;
    //找到需要插入的位置
    while(temp >1 && value < node.values[temp-1]) {
      temp = temp-1;
    }
    if(node.children[temp].n === (this.order * 2 -1) ) {
      this.split(node.children[temp], node, temp + 1);
      if (value  > node.values[temp]) {
        temp = temp + 1;
      }
    }
    this.insertNonFull(node.children[temp], value);
  }

  /**
   * Divide child node from parent into parent.values[pos-1] and parent.values[pos]
   * O(1)
   * @param {BTreeNode} child 
   * @param {BTreeNode} parent 
   * @param {number} pos 
   */
  split(child, parent, pos) {
    const newChild = new BTreeNode(child.leaf);
    newChild.tree = this.root.tree;
    // Create a new child
    // Pass values from the old child to the new
    for (let k = 1; k < this.order; k++) {
      newChild.addValue(child.removeValue(this.order));
    }
    // Trasspass child nodes from the old child to the new
    if (!child.leaf) {
      for (let k = 1; k <= this.order; k++) {
        newChild.addChild(child.deleteChild(this.order), k - 1);
      }
    }
    // Add new child to the parent
    parent.addChild(newChild, pos);
    // Pass value to parent
    parent.addValue(child.removeValue(this.order - 1));
    parent.leaf = false;
  }

  /**
   * Deletes the value from the Tree. O(log N)
   * @param {number} value 
   */
  delete(value) {
    if (this.root.n === 1 && !this.root.leaf &&
      this.root.children[0].n === this.order-1 && this.root.children[1].n === this.order -1) {
      // Check if the root can shrink the tree into its childs
      this.mergeNodes(this.root.children[1], this.root.children[0]);
      this.root = this.root.children[0];
    }
    // Start looking for the value to delete
    this.deleteFromNode(this.root, parseInt(value, 10));
  }

  /**
   * Delete a value from a node
   * @param {BTreeNode} node 
   * @param {number} value 
   */
  deleteFromNode(node, value) {
    const index = node.values.indexOf(value);
    if (index >=0) {
      // Value present in the node simple case1 叶子节点且数目也足够，直接删除
      if (node.leaf && node.n > this.order - 1) {
        // If the node is a leaf and has more than order-1 values, just delete it
        node.removeValue(node.values.indexOf(value));
        return true;
      }
      if(node.children[index].n > this.order-1 || 
        node.children[index+1].n > this.order-1) {
        // One of the immediate children has enough values to transfer
        if (node.children[index].n > this.order - 1) {
          // Replace the target value for the higher of left node.
          // Then delete that value from the child
          const predecessor = this.getMinMaxFromSubTree(node.children[index], 1);
          node.values[index] = predecessor;
          return this.deleteFromNode(node.children[index], predecessor);
        }
        const successor = this.getMinMaxFromSubTree(node.children[index+1], 0);
        node.values[index] = successor;
        return this.deleteFromNode(node.children[index+1], successor);
      }
      // Children has not enough values to transfer. Do a merge
      this.mergeNodes(node.children[index + 1], node.children[index]);
      return this.deleteFromNode(node.children[index], value);
    }
    // Value is not present in the node
    if (node.leaf) {
      // Value is not in the tree
      return false;
    }
    // Value is not present in the node, search in the children
    let nextNode = 0;
    while (nextNode < node.n && node.values[nextNode] < value) {
      nextNode++;
    }
    if (node.children[nextNode].n > this.order - 1) {
      // Child node has enough values to continue
      return this.deleteFromNode(node.children[nextNode], value);
    }
    // Child node has not enough values to continue
    // Before visiting next node transfer a value or merge it with a brother
    if ((nextNode > 0 && node.children[nextNode - 1].n > this.order - 1) ||
      (nextNode < node.n && node.children[nextNode + 1].n > this.order - 1)) {
      // One of the immediate children has enough values to transfer
      if (nextNode > 0 && node.children[nextNode - 1].n > this.order - 1) {
        this.transferValue(node.children[nextNode - 1], node.children[nextNode]);
      } else {
        this.transferValue(node.children[nextNode + 1], node.children[nextNode]);
      }
      return this.deleteFromNode(node.children[nextNode], value);
    }
    // No immediate brother with enough values.
    // Merge node with immediate one brother
    this.mergeNodes(
      nextNode > 0 ? node.children[nextNode - 1] : node.children[nextNode + 1],
      node.children[nextNode]);
    return this.deleteFromNode(node.children[nextNode], value);
  }

  /**
   * Get the lower or higher value in a sub-tree. O(log N)
   * @param {BTreeNode} node 
   * @param { 0 | 1 } max 1 for find max, 0 for min
   * @returns {number}
   */
  getMinMaxFromSubTree(node, max) {
    while (!node.leaf) {
      node = node.children[max ? node.n : 0];
    }
    return node.values[max ? node.n - 1 : 0];
  }

  /**
   * Transfer one value from the origin to the target. O(1)
   * @param {BTreeNode} origin 
   * @param {BTreeNode} target 
   */
  transferValue(origin, target) {
    const indexo = origin.parent.children.indexOf(origin);
    const indext = origin.parent.children.indexOf(target);
    if (indexo < indext) {
      target.addValue(target.parent.removeValue(indexo));
      origin.parent.addValue(origin.removeValue(origin.n-1));
      if (!origin.leaf) {
        target.addChild(origin.deleteChild(origin.children.length-1), 0);
      }
    } else {
      target.addValue(target.parent.removeValue(indext));
      origin.parent.addValue(origin.removeValue(0));
      if (!origin.leaf) {
        target.addChild(origin.deleteChild(0), target.children.length);
      }
    }
  }

  /**
   * Mix 2 nodes into one. O(1)
   * @param {BTreeNode} origin 
   * @param {BTreeNode} target 
   */
  mergeNodes(origin, target) {
    const indexo = origin.parent.children.indexOf(origin);
    const indext = target.parent.children.indexOf(target);
    target.addValue(target.parent.removeValue(Math.min(indexo, indext)));
    for (let i = origin.n - 1; i >= 0; i--) {
      target.addValue(origin.removeValue(i));
    }
    // Remove reference to origin node
    target.parent.deleteChild(indexo);
    // Transfer all the children from origin node to target
    if (!origin.leaf) {
      while (origin.children.length) {
        if (indexo > indext) {
          target.addChild(origin.deleteChild(0), target.children.length);
        } else {
          target.addChild(origin.deleteChild(origin.children.length - 1), 0);
        }
      }
    }
  }
}