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

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)算法导论习题练习——红黑树的插入和删除

最后修改:2024 年 09 月 14 日
如果觉得我的文章对你有用,请随意赞赏