【笔记】234树笔记

【笔记】234树笔记

panedioic
2022-07-07 / 0 评论 / 2 阅读 / 正在检测是否收录...

代码在这,测试是通过了。具体的细节以后再研究吧。

function Tree234Node(rootNode){
    this.rootNode = rootNode;
    this.elements = [];
    this.childs = [];
    this.debugCode = Math.floor(Math.random()*1000000);

}

function Tree234(){
    this.root = new Tree234Node(this);
    this.root.elements = [];
    this.root.childs = [];
    this.root.parentNode = 0;
}

Tree234Node.prototype.getParentNode = function(){
    let value = this.elements[0];
    let nowParentNode = 0;
    let checkingNode = this.rootNode.root;
    //console.log(value, checkingNode)
    while(true){
        //console.log('qwq77', checkingNode)
        for(let i = 0; i < checkingNode.elements.length; i += 1){
            if(checkingNode.elements[i] === value){
                return nowParentNode;
            }
        }
        if(checkingNode.childs.length === 0){
            return 0;
        }
        //console.log('qwq78')
        let nextNodePos = checkingNode.childs.length-1;
        for(let i = 0; i < checkingNode.childs.length; i += 1){
            if(checkingNode.elements[i] > value){
                nextNodePos = i;
                break;
            }
        }
        //console.log('qwq79', checkingNode.childs, checkingNode.childs.length-1, checkingNode)
        nowParentNode = checkingNode;
        checkingNode = checkingNode.childs[nextNodePos];
        //console.log('qwq80', checkingNode)
    }
}

Tree234Node.prototype.insert = function(node){
    let value = node.elements[0];
    let pos = this.elements.length;
    for(let i = 0; i < this.elements.length; i += 1){
        if(value < this.elements[i]){
            pos = i;
            break;
        }
        if(value === this.elements[i]){
            return 0;
        }
    }
    let parentNodeRef = this.getParentNode();
    if(this.elements.length <= 2){
        this.elements.splice(pos, 0, value);
        if(node.childs.length > 0){
            this.childs.splice(pos, 1);
            this.childs.splice(pos, 0, node.childs[1]);
            this.childs.splice(pos, 0, node.childs[0]);
        }
        return 0;
    }
    else {
        let pop = new Tree234Node(this.rootNode);
        pop.elements=[this.elements[1]];
        pop.childs = [new Tree234Node(this.rootNode), new Tree234Node(this.rootNode)];
        pop.childs[0].elements = [this.elements[0]];
        pop.childs[1].elements = [this.elements[2]];
        if(node.childs.length > 0){
            pop.childs[0].childs = [this.childs[0], this.childs[1]];
            pop.childs[1].childs = [this.childs[2], this.childs[3]];
        }
        let insertChildPos = pos <= 1 ? 0 : 1;
        pop.childs[insertChildPos].insert(node);
        if (parentNodeRef===0) {
            return pop;
        } else {
            return parentNodeRef.insert(pop);
        }
    }
}

Tree234.prototype.insert = function(value){
    if(this.root.elements.length === 0){
        this.root.elements = [value];
        this.root.childs = [];
        return;
    }
    // search nearest node
    let checkingNode = this.root;
    while(true){
        if(checkingNode.childs.length === 0){
            break;
        }
        let childPos = checkingNode.elements.length;
        for(let i = 0; i < checkingNode.elements.length; i += 1){
            if(value < checkingNode.elements[i]){
                childPos = i;
                break;
            }
        }
        checkingNode = checkingNode.childs[childPos];
    }
    let insertNode = new Tree234Node(this);
    insertNode.elements = [value];
    let ret = checkingNode.insert(insertNode);
    if(ret !== 0){
        this.root = ret;
    }
}

Tree234Node.prototype.printTreeRoot = function(){
    //console.log('qwq23')
    let elementList = [];
    maxLayer = 0;
    let collector = (node, layer)=>{
        //console.log('qwq24', node.debugCode)
        if(layer > maxLayer){
            maxLayer = layer;
        }
        if (node.childs.length === 0) {
            elementList.push({layer:layer,element:'['});
            for(let i = 0; i < node.elements.length; i += 1){
                elementList.push({layer:layer,element:node.elements[i]});
            }
            elementList.push({layer:layer,element:']'});
        } else {
            elementList.push({layer:layer,element:'['});
            collector(node.childs[0], layer+1);
            elementList.push({layer:layer,element:node.elements[0]});
            collector(node.childs[1], layer+1);
            if(node.elements.length === 1){
                elementList.push({layer:layer,element:']'});
                return;
            }
            elementList.push({layer:layer,element:node.elements[1]});
            collector(node.childs[2], layer+1);
            if(node.elements.length === 2){
                elementList.push({layer:layer,element:']'});
                return;
            }
            elementList.push({layer:layer,element:node.elements[2]});
            collector(node.childs[3], layer+1);
            elementList.push({layer:layer,element:']'});
            return;
        }
    }
    collector(this, 0);

    padding='          ';
    printString = '';
    for(let i = 0; i <= maxLayer; i += 1){
        for(let j = 0; j < elementList.length; j += 1){
            //console.log(elementList[j].element)
            tmp_str = elementList[j].element.toString();
            if(elementList[j].layer !== i){
                printString += padding.substr(0, tmp_str.length);
            } else {
                printString += tmp_str;
            }
            printString += ' ';
        }
        printString += '\n';
    }

    console.log(printString);
}

Tree234.prototype.printTree = function(){
    this.root.printTreeRoot();
}

Tree234Node.prototype.search = function(value){
    //console.log(this)
    for(let i = 0; i < this.elements.length; i += 1) {
        if(this.elements[i] === value){
            //console.log('qwq3')
            return this;
        }
        else if (this.elements[i] > value && this.childs.length !== 0){
            let ret = this.childs[i].search(value);
            if(ret){
                //console.log('qwq4')
                //console.log(ret)
                return ret;
            }
        }
    }
    if (this.childs.length !== 0) {
        let ret = this.childs[this.childs.length-1].search(value);
        if(ret){
            return ret;
        }
    }
}

Tree234.prototype.search = function(value){
    return this.root.search(value);
}

Tree234Node.prototype.delete = function(value){
    // Case 1: If x is in a leaf node. Here we default the element to be deleted on the leaf node.
    // Case 1.1: If x is either in a 3-node or 4-node.
    if(this.elements.length >= 2){
        //console.log('qwq31',this.elements, pos)
        for(let i = 0; i < this.elements.length; i += 1){
            if(value === this.elements[i]){
                this.elements.splice(i, 1);
                break;
            }
        }
        //console.log('qwq32',this.elements)
        return;
    }

    let parentNodeRef = this.getParentNode();
    if(parentNodeRef === 0){
        //this.elements = [this.childs[0].elements[0], this.elements[0], this.childs[1].elements[0]];
        //parentNodeRef.childs=[this.childs[0].childs[0], this.childs[0].childs[1], this.childs[1].childs[0], this.childs[1].childs[1]];
        //return;
    }
    // find pos
    let pos = -1;
    for(let i = 0; i < parentNodeRef.childs.length; i += 1){
        if(this.elements[0] === parentNodeRef.childs[i].elements[0]){
            pos = i;
        }
    }
    //console.log('qwq36', value, pos)

    // Case 1.2: If x is in a 2-node and the parent node is not a 2-node.
    //if(parentNodeRef.elements.length >= 2){
    if(true){
        let mergeDirection = pos === 0 ? 1 : 0;
        let caseType = 0;
        if(pos !== 0 && parentNodeRef.childs[pos-1].elements.length >=2){
            caseType = 1;
            mergeDirection = 0;
        }
        if(pos !== parentNodeRef.childs.length-1 && parentNodeRef.childs[pos+1].elements.length >=2){
            caseType = 1;
            mergeDirection = 1;
        }
        let parentElementPos = mergeDirection === 1 ? pos : pos-1;
        let neighborNodePos = mergeDirection === 1 ? pos+1 : pos-1;

        // Case 1.2.1: If the node containing x has 3-node or 4-node siblings
        if(caseType === 1){
            this.elements = mergeDirection === 1 ?
                [value, parentNodeRef.elements[parentElementPos]] :
                [parentNodeRef.elements[parentElementPos], value] ;
            let negElemmentPos = mergeDirection === 1 ? 0 : parentNodeRef.childs[parentElementPos].elements.length-1;
            parentNodeRef.elements[parentElementPos] = parentNodeRef.childs[neighborNodePos].elements[negElemmentPos];
            parentNodeRef.childs[neighborNodePos].elements.splice(negElemmentPos, 1);

            if(this.childs.length !== 0){
                let neighborChildPos = mergeDirection === 1 ? 0 : parentNodeRef.childs[parentElementPos].childs.length-1;
                let neighborChild = parentNodeRef.childs[neighborNodePos].childs[neighborChildPos];
                parentNodeRef.childs[neighborNodePos].childs.splice(neighborChildPos, 1);
                //console.log('qwq50', value, this.childs.length, neighborChild.elements, this.childs[0].elements)
                this.childs = mergeDirection === 1 ?
                    [this.childs[0], this.childs[1], neighborChild] :
                    [neighborChild, this.childs[0], this.childs[1]] ;
                //console.log('qwq49', value, this.childs.length, neighborChild.elements, this.childs[0].elements)
            }
            //console.log('qwq55', this.elements, parentNodeRef.elements, parentNodeRef.childs.length, parentNodeRef.childs[1].elements)
            //console.log('qwq56', this.childs.length, parentNodeRef.elements, parentNodeRef.childs[1].childs.length)
        }
        // Case 1.2.2: If both the siblings are 2-node but the parent node is either a 3-node or a 4-node
        else {
            //console.log('qwq54', parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements, parentNodeRef.elements)
            let parentElementValue = parentNodeRef.elements[parentElementPos];
            parentNodeRef.delete(parentElementValue);
            //console.log('qwq53', parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements, parentNodeRef.elements)
            let neighborNode = parentNodeRef.childs[neighborNodePos];
            parentNodeRef.childs.splice(neighborNodePos, 1);
            //console.log('qwq52', neighborNode.elements, neighborNodePos, parentNodeRef.childs[1].elements)
            this.elements = mergeDirection === 1 ?
                [value, parentElementValue, neighborNode.elements[0]] :
                [neighborNode.elements[0], parentElementValue, value] ;
            //parentNodeRef.elements.splice(parentElementPos, 1);
            //parentNodeRef.childs.splice(parentElementPos, 0, this);

            if(this.childs.length !== 0){
                //let neighborChilds = parentNodeRef.childs.splice(neighborNodePos, 1).childs;
                let neighborChilds = neighborNode.childs;
                this.childs = mergeDirection === 1 ?
                    this.childs.concat(neighborChilds) : neighborChilds.concat(this.childs) ;
                //console.log('qwq48', value, this.childs.length)
            }
        }
        this.delete(value);
        // Case 1.2.3: If both siblings and the parent node are a 2-node.
        //console.log('qwq45', value, this.elements, parentNodeRef.childs.length, parentNodeRef.getParentNode().elements)
        //console.log('qwq41', value, this.elements, parentNodeRef.childs[0].elements, parentNodeRef.elements, parentNodeRef.getParentNode().elements)
        //console.log('qwq43', value, this.elements, parentNodeRef.elements, parentNodeRef.getParentNode().elements)
        //console.log('qwq45', value, this.elements, parentNodeRef.elements, parentNodeRef.childs[0].elements, parentNodeRef.childs[1].elements)
    }
}

Tree234.prototype.delete = function(value){
    if(this.root.elements.length === 1 && this.root.childs.length === 0){
        this.root.elements = [];
        return;
    }
    let deleteNode = this.root.search(value);
    if(deleteNode.childs.length === 0){
        deleteNode.delete(value);
    } else {
        // Find the predecessor of the node containing x
        // search nearest node
        let checkingNode = deleteNode;
        let pos = 0;
        for(let i = 0; i < checkingNode.elements.length; i += 1){
            if(value === checkingNode.elements[i]){
                pos = i;
                break;
            }
        }
        checkingNode = checkingNode.childs[pos];
        while(true){
            if(checkingNode.childs.length === 0){
                break;
            }
            checkingNode = checkingNode.childs[checkingNode.childs.length-1];
        }
        let predecessorValue = checkingNode.elements[checkingNode.elements.length-1];
        checkingNode.delete(predecessorValue);
        deleteNode.elements[pos] = predecessorValue;
    }
    if(this.root.childs.length === 2 && this.root.childs[0].elements.length === 1 && this.root.childs[1].elements.length === 1){
        this.root.elements = [this.root.childs[0].elements[0], this.root.elements[0], this.root.childs[1].elements[0]];
        if(this.root.childs[0].childs.length !== 0){
            this.root.childs = [this.root.childs[0].childs[0], this.root.childs[0].childs[1]
                , this.root.childs[1].childs[0], this.root.childs[1].childs[1]];
        } else {
            this.root.childs = [];
        }
    }
}

References

[硬核图解红黑树并手写实现
](https://juejin.cn/post/6947666874226180133)B-Trees visualization
2-3-4 Trees: A Visual Introduction
2-3-4 Trees algorithmtutor.com
[【考研】数据结构:红黑树(2022新增考点)
](https://blog.csdn.net/qq_34438969/article/details/121010725?spm=1001.2101.3001.6661.1&utm_medium=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-121010725-blog-78073742.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-2~default~CTRLIST~default-1-121010725-blog-78073742.pc_relevant_default&utm_relevant_index=1)算法导论习题练习——红黑树的插入和删除

0

评论 (0)

取消