bTree.js

  1. import { BTreeNode } from './node.js';
  2. import { EXIST_VALUE, INVALID_VALUE, NON_EXIST_VALUE } from './error.js';
  4. /**
  5.  * B - Tree 클래스
  6.  */
  7. class BTree {
  8.   /**
  9.    * BTree 클래스의 생성자로 현재 n이 홀수인 Btree만 구현되어 있습니다.
  10.    * @param {*} limit
  11.    * @throws {INVALID_VALUE} n이 number타입이 아니거나 짝수인 경우 예외 발생.
  12.    */
  13.   constructor(limit) {
  14.     if (typeof limit !== 'number' || limit % 2 === 0 || limit <= 1) throw new Error(INVALID_VALUE);
  16.     this.root = null;
  17.     this.limit = limit;
  18.     this.size = 0;
  19.   }
  21.   /**
  22.    * remove 메소드에서 사용되는 swap 헬퍼 함수.
  23.    * @param {BTreeNode} delNode 삭제될 노드.
  24.    * @param {number} index 삭제를 위해 검색을 시작할 자식노드의 index.
  25.    * @returns {*} 삭제할 값을 리턴.
  26.    */
  27.   _swap(delNode, index) {
  28.     let subsParent = delNode;
  29.     let subsNode = delNode.rightChildOf(index);
  31.     while (subsNode.leftChildOf(0) && subsNode.leftChildOf(0) instanceof BTreeNode) {
  32.       subsParent = subsNode;
  33.       subsNode = subsParent.leftChildOf(0);
  34.     }
  36.     delNode.values[index] = subsNode.value(0);
  38.     return subsNode.value(0);
  39.   }
  41.   /**
  42.    * 하나의 노드를 분할한다. 분할된 노드의 부모 노드를 리턴한다.
  43.    * @param {BTreeNode} parent
  44.    * @param {number} key 기준이 되는 value값
  45.    * @returns {BTreeNode} 분할된 노드의 부모 노드.
  46.    */
  47.   _split(parent, key) {
  48.     let current;
  50.     if (!parent) {
  51.       // 분할 대상 노드가 루트 노드인 경우 (부모가 없는 경우)
  52.       current = this.root;
  54.       const leftChildNode = new BTreeNode(this.limit);
  56.       let i;
  57.       for (i = 0; i < Math.floor(this.limit / 2); i += 1) {
  58.         leftChildNode.values[i] = current.value(i);
  59.         leftChildNode.children[i] = current.leftChildOf(i);
  60.       }
  61.       leftChildNode.children[i] = current.leftChildOf(i);
  62.       leftChildNode.valueLength = Math.floor(this.limit / 2);
  64.       const midValue = current.value(i);
  66.       const rightChildNode = new BTreeNode(this.limit);
  67.       let j;
  68.       for (j = 0, i += 1; i < this.limit; i += 1, j += 1) {
  69.         rightChildNode.values[j] = current.value(i);
  70.         rightChildNode.children[j] = current.leftChildOf(i);
  71.       }
  72.       rightChildNode.children[j] = current.leftChildOf(i);
  73.       rightChildNode.valueLength = j;
  75.       current.clear();
  77.       current.addValue(midValue, leftChildNode, rightChildNode);
  78.     } else {
  79.       // 분할 대상 노드가 루트 노드가 아닌 경우 (부모가 있는 경우)
  80.       let i;
  81.       for (i = 0; parent.value(i) < key; i += 1);
  82.       current = parent.leftChildOf(i);
  84.       let k = Math.floor(this.limit / 2);
  85.       const midValue = current.value(k);
  87.       const rightChildNode = new BTreeNode(this.limit);
  88.       let j;
  89.       for (j = 0, k += 1; k < this.limit; k += 1, j += 1) {
  90.         rightChildNode.values[j] = current.value(k);
  91.         rightChildNode.children[j] = current.leftChildOf(k);
  92.       }
  93.       rightChildNode.children[j] = current.leftChildOf(k);
  94.       rightChildNode.valueLength = j;
  96.       current.values.splice(Math.floor(this.limit / 2));
  97.       current.children.splice(Math.floor(this.limit / 2) + 1);
  98.       current.valueLength = Math.floor(this.limit / 2);
  100.       parent.addValue(midValue, current, rightChildNode);
  102.       current = parent;
  103.     }
  105.     return current;
  106.   }
  108.   /**
  109.    * 형제 노드에게서 value를 빌려온다.
  110.    * @param {BTreeNode} parent
  111.    * @param {number} index
  112.    * @returns {boolean} 빌려 오는 것이 가능한지 여부를 리턴한다.
  113.    */
  114.   _borrowKey(parent, index) {
  115.     let fromIndex = index + 1;
  116.     if (index === parent.size()) fromIndex = index - 1;
  118.     const from = parent.leftChildOf(fromIndex);
  119.     const to = parent.leftChildOf(index);
  121.     if (from.size() <= Math.floor(this.limit / 2)) return false;
  123.     if (fromIndex > index) {
  124.       // 오른쪽 형제에게 빌려오는 경우
  125.       to.addValue(parent.value(index), null, from.leftChildOf(0));
  126.       parent.values[index] = from.value(0);
  127.       from.removeValue(0);
  128.     } else {
  129.       // 왼쪽 형제에게 빌려오는 경우
  130.       to.addValue(parent.value(index - 1), from.leftChildOf(from.size()), null);
  131.       parent.values[index - 1] = from.value(from.size() - 1);
  132.       from.removeValue(from.size() - 1);
  133.     }
  135.     return true;
  136.   }
  138.   /**
  139.    * 형제 노드와 합친다.
  140.    * @param {BTreeNode} parent
  141.    * @param {number} index
  142.    * @returns {BTreeNode} 합쳐진 노드를 리턴한다.
  143.    */
  144.   _bindNode(parent, index) {
  145.     if (index === parent.size()) index -= 1;
  147.     const left = parent.leftChildOf(index);
  148.     const right = parent.rightChildOf(index);
  150.     left.addValue(parent.value(index), null, null);
  151.     let i;
  152.     let j;
  153.     for (i = 0, j = left.size(); i < right.size(); i += 1, j += 1) {
  154.       left.values[j] = right.value(i);
  155.       left.children[j] = right.children[i];
  156.     }
  157.     left.children[j] = right.children[i];
  158.     left.valueLength = left.size() + right.size();
  160.     parent.removeValue(index);
  161.     parent.children[index] = left;
  163.     // 부모 노드가 뿌리노드인 경우
  164.     if (!parent.size()) this.root = left;
  166.     return left;
  167.   }
  169.   /**
  170.    * 현재 BTree에 있는 노드 개수를 리턴한다.
  171.    * @returns {number}
  172.    */
  173.   size() {
  174.     return this.size;
  175.   }
  177.   /**
  178.    * b-tree 에서 해당 값을 찾는다.
  179.    * @param {*} value
  180.    * @returns {BTreeNode} 찾은 노드를 반환한다. 값이 존재하지 않으면 false를 반환한다.
  181.    */
  182.   find(value) {
  183.     let targetNode = this.root;
  185.     while (targetNode && targetNode.findValue(value) < 0) {
  186.       let i;
  187.       for (i = 0; i < targetNode.size() && targetNode.value(i) < value; i += 1);
  189.       targetNode = targetNode.leftChildOf(i);
  190.     }
  192.     if (!targetNode) return false;
  194.     return targetNode;
  195.   }
  197.   /**
  198.    * b-tree에 주어진 값을 삽입한다.
  199.    * @param {*} value
  200.    * @throws {EXIST_VALUE} 이미 값이 존재하면 예외 발생.
  201.    * @returns {BTree} 값이 삽입된 자기 자신 리턴.
  202.    */
  203.   insert(value) {
  204.     if (!this.root) this.root = new BTreeNode(this.limit);
  205.     let current = this.root;
  206.     let parent = null;
  208.     while (current) {
  209.       if (current.findValue(value) >= 0) throw Error(EXIST_VALUE);
  211.       if (current.size() >= this.limit) {
  212.         current = this._split(parent, value);
  213.       }
  215.       parent = current;
  216.       let i;
  217.       for (i = 0; i < current.size() && current.value(i) < value; i += 1);
  218.       current = current.leftChildOf(i);
  219.     }
  221.     parent.addValue(value, undefined, undefined);
  222.     this.size += 1;
  223.     return this;
  224.   }
  226.   /**
  227.    * b-tree 에서 주어진 값을 삭제한다.
  228.    * @param {*} value
  229.    * @throws {NON_EXIST_VALUE} 주어진 값이 존재하지 않으면 예외 발생.
  230.    * @returns {boolean} 삭제한 뒤 true를 반환한다.
  231.    */
  232.   remove(value) {
  233.     let parent = null;
  234.     let current = this.root;
  236.     let i = 0;
  237.     while (current) {
  238.       if (parent && current.size() <= Math.floor(this.limit / 2)) {
  239.         if (!this._borrowKey(parent, i)) current = this._bindNode(parent, i);
  240.       }
  242.       if (current.findValue(value) >= 0) {
  243.         if (!current.leftChildOf(0)) break; // current 가 leaf 노드 인 경우
  244.         value = this._swap(current, current.findValue(value)); // leaf 노드가 아니면 swap 한 다음, 다시 새로운 value를 지우는 알고리즘 실행
  245.       }
  247.       parent = current;
  249.       for (i = 0; i < current.size() && current.value(i) <= value; i += 1);
  250.       current = current.leftChildOf(i);
  251.     }
  253.     if (!current) throw new Error(NON_EXIST_VALUE); // break 하지 못한 경우, value를 트리에서 찾지 못한 것이므로 false 리턴.
  255.     if (current.size() <= Math.floor(this.limit / 2)) {
  256.       if (!this._borrowKey(parent, i)) current = this._bindNode(parent, i);
  257.     }
  259.     current.removeValue(current.findValue(value));
  260.     this.size -= 1;
  261.     return true;
  262.   }
  264.   // generators * * * * * * * * * * * * *
  266.   /**
  267.    * dequeue 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  268.    * @generator
  269.    * @param {BTreeNode} parent
  270.    * @param {number} index
  271.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  272.    * @returns {boolean} 빌려 오는 것이 가능한지 여부를 리턴한다.
  273.    */
  274.   *_borrowKeyGen(parent, index) {
  275.     let fromIndex = index + 1;
  276.     if (index === parent.size()) fromIndex = index - 1;
  278.     const from = parent.leftChildOf(fromIndex);
  279.     const to = parent.leftChildOf(index);
  281.     if (from.size() <= Math.floor(this.limit / 2)) {
  282.       return false;
  283.     }
  284.     yield true;
  286.     to.colored = 'blue';
  287.     from.colored = 'green';
  289.     yield this;
  291.     delete to.colored;
  292.     delete from.colored;
  294.     if (fromIndex > index) {
  295.       to.valuesColor[to.size() - 1] = 'blue';
  296.       parent.valuesColor[index] = 'orange';
  297.       from.valuesColor[0] = 'green';
  299.       yield this;
  301.       to.valuesColor = [];
  302.       parent.valuesColor = [];
  303.       from.valuesColor = [];
  305.       // 오른쪽 형제에게 빌려오는 경우
  306.       to.addValue(parent.value(index), null, from.leftChildOf(0));
  307.       parent.values[index] = from.value(0);
  308.       from.removeValue(0);
  310.       to.valuesColor[to.size() - 2] = 'blue';
  311.       to.valuesColor[to.size() - 1] = 'orange';
  312.       parent.valuesColor[index] = 'green';
  313.     } else {
  314.       to.valuesColor[0] = 'blue';
  315.       parent.valuesColor[index - 1] = 'orange';
  316.       from.valuesColor[from.size() - 1] = 'green';
  318.       yield this;
  320.       to.valuesColor = [];
  321.       parent.valuesColor = [];
  322.       from.valuesColor = [];
  324.       // 왼쪽 형제에게 빌려오는 경우
  325.       to.addValue(parent.value(index - 1), from.leftChildOf(from.size()), null);
  326.       parent.values[index - 1] = from.value(from.size() - 1);
  327.       from.removeValue(from.size() - 1);
  329.       to.valuesColor[1] = 'blue';
  330.       to.valuesColor[0] = 'orange';
  331.       parent.valuesColor[index - 1] = 'green';
  332.     }
  334.     const temp = this;
  336.     to.valuesColor = [];
  337.     parent.valuesColor = [];
  339.     return temp;
  340.   }
  342.   /**
  343.    * _bindNode 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  344.    * @generator
  345.    * @param {BTreeNode} parent
  346.    * @param {number} index
  347.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  348.    * @returns {BTreeNode} 합쳐진 노드를 리턴한다.
  349.    */
  350.   *_bindNodeGen(parent, index) {
  351.     let isLeft = true;
  353.     if (index === parent.size()) {
  354.       index -= 1;
  355.       isLeft = false;
  356.     }
  358.     const left = parent.leftChildOf(index);
  359.     const right = parent.rightChildOf(index);
  361.     left.colored = isLeft ? 'blue' : 'green';
  362.     right.colored = isLeft ? 'green' : 'blue';
  363.     parent.valuesColor[index] = 'orange';
  365.     yield this;
  367.     delete left.colored;
  368.     delete right.colored;
  369.     parent.valuesColor = [];
  371.     left.addValue(parent.value(index), null, null);
  372.     let i;
  373.     let j;
  374.     for (i = 0, j = left.size(); i < right.size(); i += 1, j += 1) {
  375.       left.values[j] = right.value(i);
  376.       left.children[j] = right.children[i];
  377.     }
  378.     left.children[j] = right.children[i];
  379.     left.valueLength = left.size() + right.size();
  381.     parent.removeValue(index);
  382.     parent.children[index] = left;
  384.     // 부모 노드가 뿌리노드인 경우
  385.     if (!parent.size()) this.root = left;
  387.     const mid = Math.floor(this.limit / 2);
  388.     for (let j = 0; j < this.limit; j += 1) {
  389.       if (j < mid) {
  390.         left.valuesColor[j] = isLeft ? 'blue' : 'green';
  391.       } else if (j === mid) {
  392.         left.valuesColor[j] = 'orange';
  393.       } else {
  394.         left.valuesColor[j] = isLeft ? 'green' : 'blue';
  395.       }
  396.     }
  398.     yield this;
  399.     left.valuesColor = [];
  401.     return left;
  402.   }
  404.   /**
  405.    * _swap 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  406.    * @generator
  407.    * @param {BTreeNode} delNode 삭제될 노드.
  408.    * @param {number} index 삭제를 위해 검색을 시작할 자식노드의 index.
  409.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  410.    * @returns {*} 삭제할 값을 리턴.
  411.    */
  412.   *_swapGen(delNode, index) {
  413.     let subsParent = delNode;
  414.     let subsNode = delNode.rightChildOf(index);
  416.     delNode.valuesColor[index] = 'blue';
  417.     subsNode.colored = 'green';
  419.     yield this;
  421.     delete subsNode.colored;
  423.     while (subsNode.leftChildOf(0) && subsNode.leftChildOf(0) instanceof BTreeNode) {
  424.       subsParent = subsNode;
  425.       subsNode = subsParent.leftChildOf(0);
  427.       subsNode.colored = 'green';
  428.       yield this;
  430.       delete subsNode.colored;
  431.     }
  433.     subsNode.valuesColor[0] = 'green';
  434.     yield this;
  436.     delNode.valuesColor[index] = 'white';
  437.     yield this;
  439.     delNode.values[index] = subsNode.value(0);
  441.     delNode.valuesColor[index] = 'green';
  442.     yield this;
  444.     delNode.valuesColor = [];
  445.     subsNode.valuesColor = [];
  447.     yield this;
  449.     return subsNode.value(0);
  450.   }
  452.   /**
  453.    * _swap 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  454.    * @generator
  455.    * @param {BTreeNode} parent
  456.    * @param {number} key 기준이 되는 value 값
  457.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  458.    * @returns {BTreeNode} 분할된 노드의 부모 노드.
  459.    */
  460.   *_splitGen(parent, key) {
  461.     let current;
  463.     if (!parent) {
  464.       // 분할 대상 노드가 루트 노드인 경우 (부모가 없는 경우)
  465.       current = this.root;
  467.       const mid = Math.floor(this.limit / 2);
  468.       current.values.forEach((v, index) => {
  469.         if (index < mid) {
  470.           current.valuesColor[index] = 'green';
  471.         } else if (index === mid) {
  472.           current.valuesColor[index] = 'blue';
  473.         } else {
  474.           current.valuesColor[index] = 'orange';
  475.         }
  476.       });
  477.       yield this;
  479.       current.valuesColor = [];
  481.       const leftChildNode = new BTreeNode(this.limit);
  483.       let i;
  484.       for (i = 0; i < Math.floor(this.limit / 2); i += 1) {
  485.         leftChildNode.values[i] = current.value(i);
  486.         leftChildNode.children[i] = current.leftChildOf(i);
  487.       }
  488.       leftChildNode.children[i] = current.leftChildOf(i);
  489.       leftChildNode.valueLength = Math.floor(this.limit / 2);
  491.       const midValue = current.value(i);
  493.       const rightChildNode = new BTreeNode(this.limit);
  494.       let j;
  495.       for (j = 0, i += 1; i < this.limit; i += 1, j += 1) {
  496.         rightChildNode.values[j] = current.value(i);
  497.         rightChildNode.children[j] = current.leftChildOf(i);
  498.       }
  499.       rightChildNode.children[j] = current.leftChildOf(i);
  500.       rightChildNode.valueLength = j;
  502.       current.clear();
  504.       current.addValue(midValue, leftChildNode, rightChildNode);
  506.       current.valuesColor[0] = 'blue';
  508.       current.leftChildOf(0).values.forEach((v, index) => {
  509.         current.leftChildOf(0).valuesColor[index] = 'green';
  510.       });
  512.       current.rightChildOf(0).values.forEach((v, index) => {
  513.         current.rightChildOf(0).valuesColor[index] = 'orange';
  514.       });
  516.       yield this;
  518.       current.valuesColor = [];
  519.       current.leftChildOf(0).valuesColor = [];
  520.       current.rightChildOf(0).valuesColor = [];
  521.     } else {
  522.       // 분할 대상 노드가 루트 노드가 아닌 경우 (부모가 있는 경우)
  523.       let i;
  524.       for (i = 0; parent.value(i) < key; i += 1);
  525.       current = parent.leftChildOf(i);
  527.       const mid = Math.floor(this.limit / 2);
  528.       current.values.forEach((v, index) => {
  529.         if (index < mid) {
  530.           current.valuesColor[index] = 'green';
  531.         } else if (index === mid) {
  532.           current.valuesColor[index] = 'blue';
  533.         } else {
  534.           current.valuesColor[index] = 'orange';
  535.         }
  536.       });
  537.       yield this;
  539.       current.valuesColor = [];
  541.       let k = Math.floor(this.limit / 2);
  542.       const midValue = current.value(k);
  544.       const rightChildNode = new BTreeNode(this.limit);
  545.       let j;
  546.       for (j = 0, k += 1; k < this.limit; k += 1, j += 1) {
  547.         rightChildNode.values[j] = current.value(k);
  548.         rightChildNode.children[j] = current.leftChildOf(k);
  549.       }
  550.       rightChildNode.children[j] = current.leftChildOf(k);
  551.       rightChildNode.valueLength = j;
  553.       current.values.splice(Math.floor(this.limit / 2));
  554.       current.children.splice(Math.floor(this.limit / 2) + 1);
  555.       current.valueLength = Math.floor(this.limit / 2);
  557.       parent.addValue(midValue, current, rightChildNode);
  559.       current = parent;
  561.       const pi = current.findValue(midValue);
  563.       current.valuesColor[pi] = 'blue';
  565.       current.leftChildOf(pi).values.forEach((v, index) => {
  566.         current.leftChildOf(pi).valuesColor[index] = 'green';
  567.       });
  569.       current.rightChildOf(pi).values.forEach((v, index) => {
  570.         current.rightChildOf(pi).valuesColor[index] = 'orange';
  571.       });
  573.       yield this;
  575.       current.valuesColor = [];
  576.       current.leftChildOf(pi).valuesColor = [];
  577.       current.rightChildOf(pi).valuesColor = [];
  578.     }
  580.     return current;
  581.   }
  583.   /**
  584.    * insert 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  585.    * @generator
  586.    * @param {*} value
  587.    * @throws {EXIST_VALUE} 이미 값이 존재하면 예외 발생.
  588.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  589.    * @returns {BTree} 값이 삽입된 자기 자신 리턴.
  590.    */
  591.   *insertGen(value) {
  592.     if (!this.root) this.root = new BTreeNode(this.limit);
  593.     let current = this.root;
  594.     let parent = null;
  596.     while (current) {
  597.       current.colored = 'blue';
  598.       yield this;
  599.       delete current.colored;
  601.       if (current.findValue(value) >= 0) throw Error(EXIST_VALUE);
  603.       if (current.size() >= this.limit) {
  604.         current = yield* this._splitGen(parent, value);
  605.       }
  607.       parent = current;
  608.       let i;
  609.       for (i = 0; i < current.size() && current.value(i) < value; i += 1) {
  610.         current.valuesColor[i] = 'blue';
  611.         yield this;
  612.         current.valuesColor = [];
  613.       }
  614.       current = current.leftChildOf(i);
  615.     }
  617.     parent.addValue(value, undefined, undefined);
  618.     this.size += 1;
  619.     return this;
  620.   }
  622.   /**
  623.    * remove 메소드의 진행 상태를 generate 하는 제너레이터 함수.
  624.    * @generator
  625.    * @param {*} value
  626.    * @throws {NON_EXIST_VALUE} 주어진 값이 존재하지 않으면 예외 발생.
  627.    * @yields {BTree} 진행 상태가 시각적으로 표시된 자기 자신.
  628.    * @returns {boolean} 삭제한 뒤 true를 반환한다.
  629.    */
  630.   *removeGen(value) {
  631.     let parent = null;
  632.     let current = this.root;
  634.     let i = 0;
  635.     while (current) {
  636.       current.colored = 'blue';
  637.       yield this;
  638.       delete current.colored;
  640.       if (parent && current.size() <= Math.floor(this.limit / 2)) {
  641.         const bkIter = this._borrowKeyGen(parent, i);
  642.         if (bkIter.next().value) {
  643.           yield* bkIter;
  644.         } else {
  645.           current = yield* this._bindNodeGen(parent, i);
  646.         }
  647.       }
  649.       if (current.findValue(value) >= 0) {
  650.         if (!current.leftChildOf(0)) break; // current 가 leaf 노드 인 경우
  651.         value = yield* this._swapGen(current, current.findValue(value));
  652.       }
  654.       parent = current;
  656.       for (i = 0; i < current.size() && current.value(i) <= value; i += 1) {
  657.         current.valuesColor[i] = 'blue';
  658.         yield this;
  659.         current.valuesColor = [];
  660.       }
  661.       current = current.leftChildOf(i);
  662.     }
  664.     if (!current) throw new Error(NON_EXIST_VALUE); // break 하지 못한 경우, value를 트리에서 찾지 못한 것이므로 false 리턴.
  666.     if (current.size() <= Math.floor(this.limit / 2)) {
  667.       const bkIter = this._borrowKeyGen(parent, i);
  668.       if (bkIter.next().value) {
  669.         yield* bkIter;
  670.       } else {
  671.         current = yield* this._bindNodeGen(parent, i);
  672.       }
  673.     }
  675.     current.colored = 'blue';
  676.     yield this;
  677.     delete current.colored;
  679.     current.removeValue(current.findValue(value));
  680.     this.size -= 1;
  681.     return this;
  682.   }
  683. }
  685. export { BTree };