2-3-4树

摘要：因为是大于，因此放右子树的结点中。第二层右子树会变成，，第三层的，再分裂，将加到最右边。合并子树的根与上层结点决定哪个子树要添加如果待插入的节点不是节点，那么直接在该节点插入

function Node(key, parent){
   this.parent = null;
   this.keys = [key];
   this.children = []
}

插入2

if(!this.root){
   this.root = new Node(2)
}

插入3

var node = this.search(3);
node.keys.push(3)
node.keys.sort()

插入1

注意这里会排序

var node = this.search(3);
node.keys.push(3)
node.keys.sort()

插入4

var keys = node.keys
if(keys.length === 3){
    var top = new Node(keys[1])
    var left = new Node(keys[0], top);
    var right = new Node(keys[2], top);
    top.children.push(left, right)
    var add = key < keys[1] ? left: right;
    add.keys.push(key)
    add.keys.sort()
}

这时节点已经满4个key，为4结点（实际上4始终没有放进去这个节点中），需要进行分裂，首先，根据原来的3结点，取得中间值2，新生成一个Node，将剩下的两个key，成为它的左右子树，然后4插入到右子树中。因为4是大于2，因此放右子树的结点中。

插入5

这时找到右子树，成为3结点，key为［3，4，5］

var parent = node.parent;
pushToParent(parent, keys[1])
var children = parent.children;
var index = children.indexOf(node)
var left = new Node(keys[0],parent)
var right = new Node(keys[1],parent)
children.splice(index,1, left, right)

插入6

这次也放右边，但是已经满了，需要将4，放到其父亲，变成 2，4. 然后当前结点分裂成2个， 现在有3个孩子，6放到最右边。

插入7

插入8

与上面一样，没有惊喜

插入9

插入10

这时，[7,8,9]已经满了，需要将8放上去，这时发现，［2,4,6］也满了，只好将4抽出来，变成新的根。第二层右子树会变成［6，8］，第三层的［7，9］再分裂，将10加到最右边。

因此我们需要修改putKeyToParent方法，如果返回两个节点，那么它们就会平分孩子。

插入11

插入12

插入13

插入14

完整的代码如下：

   class Node {
      constructor(key, parent) {
        this.keys = [key]
        this.children = []
        this.parent = parent
      }
      isLeaf(){
          return !this.children[0]
      }
      addKeys(key){
          this.keys.push(key)
          this.keys.sort(function(a, b){
              return a - b
          })
      }
    }
    class Tree234{
        constructor(){
            this.root = null
        }
        search(node, key){
            if(node.isLeaf()){
                return node
            }
            var keys = node.keys
            for(var i = 0, n = keys.length; i < n; i++){
                if(key < keys[i]){
                   return this.search(node.children[i], key)
                }
            }
            return this.search(node.children[i], key)
        }
        insert(key){
            if(!this.root){//没有根节点
                this.root = new Node(key)
            }else{
                var node = this.search(this.root, key)
                insertNode(node, key, this)
            }
        }
     
    }
    function insertNode(node, key, tree){
        var keys = node.keys;
        if( keys.length === 3){
            var middle = keys[1], parent = node.parent, p
            //步骤1，确认新的父节点
            if(!parent){ 
                p = tree.root = new Node(middle)
                p.children = [node] //用于步骥2
            }else{
                p = insertNode(parent, middle, tree)
            }
             //步骤2，将目标节点拆成两个节点，它们的key为原keys[0], keys[1]
            var children = p.children
            var left = new Node(keys[0],p)
            var right = new Node(keys[2],p)
            children.splice(children.indexOf(node),1, left, right)//原位置替换
            //步骤3 将目标节点的children均匀分成 新生成的节点（只有在4结点的情况才这样做）
            if(node.children.length === 4){
                node.children[0].parent = left
                node.children[1].parent = left
                left.children = [ node.children[0], node.children[1]]
                node.children[2].parent = right
                node.children[3].parent = right
                right.children = [ node.children[2], node.children[3]]
            }
            //步骤4，添加新key
            var target = key < keys[0] ? left : right
            target.addKeys(key)
            return target
        }else{
            node.addKeys(key)
            return node
        }
    }
    var t = new Tree234()
    t.insert(2)
    t.insert(3)
    t.insert(1)
    t.insert(4)
    t.insert(5)
    t.insert(6)
    t.insert(7)
    t.insert(8)
    t.insert(9)
   
    t.insert(10)
    t.insert(11)
    t.insert(12)
    t.insert(13)
    t.insert(14)
    console.log(t)

另一个思路，碰到4结点就先拆成三个2结点，然后让这个子树的根与上面的结点进行合并。

      class Node {
            constructor(key, parent) {
                this.keys = [key]
                this.children = []
                this.parent = parent
            }
            isLeaf() {
                return !this.children[0]
            }
            addKeys(key) {
                //(1)如果2-3-4树中已存在当前插入的key，则插入失败，
                //否则最终一定是在叶子节点中进行插入操作
                if (!this.keys.includes(key)) {
                    this.keys.push(key)
                    this.keys.sort(function (a, b) {
                        return a - b
                    })
                }

            }
        }
        class Tree234 {
            constructor() {
                this.root = null
            }
            search(node, key) {
                if (node.isLeaf()) {
                    return node
                }
                var keys = node.keys
                for (var i = 0, n = keys.length; i < n; i++) {
                    if (key < keys[i]) {
                        return this.search(node.children[i], key)
                    }
                }
                return this.search(node.children[i], key)
            }
            insert(key) {
                if (!this.root) {//没有根节点
                    this.root = new Node(key)
                } else {
                    var node = this.search(this.root, key)
                    insertNode(node, key, this)
                }
            }
        }

        function split(keys) { //将4结点的三个key分裂成三个2结吉
            var middle = keys[1]
            var top = new Node(middle)//一个临时结点
            var left = new Node(keys[0], top)
            var right = new Node(keys[2], top)
            return [top, left, right]
        }
        function insertNode(node, key, tree) {
            var keys = node.keys;
            if (keys.length === 3) {
                var [top, left, right] = split(keys)
                top.children = [left, right]
                var parent = node.parent
                //(3)如果待插入的节点是个4节点，那么应该先分裂该节点然后再插入。
                //一个4节点可以分裂成一个根节点和两个子节点（这三个节点各含一个key）
                if (node.children.length === 4) {//是4节点
                    node.children[0].parent = left
                    node.children[1].parent = left
                    left.children = [node.children[0], node.children[1]]
                    node.children[2].parent = right
                    node.children[3].parent = right
                    right.children = [node.children[2], node.children[3]]
                }
                if (!parent) {
                    tree.root = top
                } else {
                    //我们把分裂形成的根节点中的key看成向上层插入的key，然后重复第2步和第3步。
                    var newParent = insertNode(parent, top.keys[0], tree)
                    left.parent = newParent
                    right.parent = newParent
                    //合并子树的根(top)与上层结点（node）
                    var index = newParent.children.indexOf(node)
                    newParent.children.splice(index, 1, left, right)
                }
                //决定哪个子树要添加key
                node = key < keys[0] ? left : right
            }
            //(2)如果待插入的节点不是4节点，那么直接在该节点插入
            node.addKeys(key)
            return node

        }
        var t = new Tree234()
        t.insert(2)
        t.insert(3)
        t.insert(1)
        t.insert(4)
        t.insert(5)
        t.insert(6)
        t.insert(7)

        t.insert(8)
        t.insert(9)

        t.insert(10)
        t.insert(11)
        t.insert(12)
        t.insert(13)
        t.insert(14)
        console.log(t)