2-3-4樹

Me_Kun 發(fā)布于2019-08-21 18:34 / 1612人閱讀

摘要：因?yàn)槭谴笥?，因此放右子樹的結(jié)點(diǎn)中。第二層右子樹會(huì)變成，，第三層的，再分裂，將加到最右邊。合并子樹的根與上層結(jié)點(diǎn)決定哪個(gè)子樹要添加如果待插入的節(jié)點(diǎn)不是節(jié)點(diǎn)，那么直接在該節(jié)點(diǎn)插入

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

注意這里會(huì)排序

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()
}

這時(shí)節(jié)點(diǎn)已經(jīng)滿4個(gè)key，為4結(jié)點(diǎn)（實(shí)際上4始終沒有放進(jìn)去這個(gè)節(jié)點(diǎn)中），需要進(jìn)行分裂，首先，根據(jù)原來(lái)的3結(jié)點(diǎn)，取得中間值2，新生成一個(gè)Node，將剩下的兩個(gè)key，成為它的左右子樹，然后4插入到右子樹中。因?yàn)?是大于2，因此放右子樹的結(jié)點(diǎn)中。

插入5

這時(shí)找到右子樹，成為3結(jié)點(diǎn)，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

這次也放右邊，但是已經(jīng)滿了，需要將4，放到其父親，變成 2，4. 然后當(dāng)前結(jié)點(diǎn)分裂成2個(gè)，現(xiàn)在有3個(gè)孩子，6放到最右邊。

插入7

插入8

與上面一樣，沒有驚喜

插入9

插入10

這時(shí)，[7,8,9]已經(jīng)滿了，需要將8放上去，這時(shí)發(fā)現(xiàn)，［2,4,6］也滿了，只好將4抽出來(lái)，變成新的根。第二層右子樹會(huì)變成［6，8］，第三層的［7，9］再分裂，將10加到最右邊。

因此我們需要修改putKeyToParent方法，如果返回兩個(gè)節(jié)點(diǎn)，那么它們就會(huì)平分孩子。

插入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){//沒有根節(jié)點(diǎn)
                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，確認(rèn)新的父節(jié)點(diǎn)
            if(!parent){ 
                p = tree.root = new Node(middle)
                p.children = [node] //用于步驥2
            }else{
                p = insertNode(parent, middle, tree)
            }
             //步驟2，將目標(biāo)節(jié)點(diǎn)拆成兩個(gè)節(jié)點(diǎn)，它們的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 將目標(biāo)節(jié)點(diǎn)的children均勻分成 新生成的節(jié)點(diǎn)（只有在4結(jié)點(diǎn)的情況才這樣做）
            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)

另一個(gè)思路，碰到4結(jié)點(diǎn)就先拆成三個(gè)2結(jié)點(diǎn)，然后讓這個(gè)子樹的根與上面的結(jié)點(diǎn)進(jìn)行合并。

      class Node {
            constructor(key, parent) {
                this.keys = [key]
                this.children = []
                this.parent = parent
            }
            isLeaf() {
                return !this.children[0]
            }
            addKeys(key) {
                //(1)如果2-3-4樹中已存在當(dāng)前插入的key，則插入失敗，
                //否則最終一定是在葉子節(jié)點(diǎn)中進(jìn)行插入操作
                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) {//沒有根節(jié)點(diǎn)
                    this.root = new Node(key)
                } else {
                    var node = this.search(this.root, key)
                    insertNode(node, key, this)
                }
            }
        }

        function split(keys) { //將4結(jié)點(diǎn)的三個(gè)key分裂成三個(gè)2結(jié)吉
            var middle = keys[1]
            var top = new Node(middle)//一個(gè)臨時(shí)結(jié)點(diǎn)
            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)如果待插入的節(jié)點(diǎn)是個(gè)4節(jié)點(diǎn)，那么應(yīng)該先分裂該節(jié)點(diǎn)然后再插入。
                //一個(gè)4節(jié)點(diǎn)可以分裂成一個(gè)根節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)（這三個(gè)節(jié)點(diǎn)各含一個(gè)key）
                if (node.children.length === 4) {//是4節(jié)點(diǎn)
                    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 {
                    //我們把分裂形成的根節(jié)點(diǎn)中的key看成向上層插入的key，然后重復(fù)第2步和第3步。
                    var newParent = insertNode(parent, top.keys[0], tree)
                    left.parent = newParent
                    right.parent = newParent
                    //合并子樹的根(top)與上層結(jié)點(diǎn)（node）
                    var index = newParent.children.indexOf(node)
                    newParent.children.splice(index, 1, left, right)
                }
                //決定哪個(gè)子樹要添加key
                node = key < keys[0] ? left : right
            }
            //(2)如果待插入的節(jié)點(diǎn)不是4節(jié)點(diǎn)，那么直接在該節(jié)點(diǎn)插入
            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)