代码在这,测试是通过了。具体的细节以后再研究吧。
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)