保存成html打开控制台就可以看到
这个是在我掌握了C++的红黑树以后重新复习的一个小代码
<script>
var rbtree={
node:function(key,val){ //新建一个节点
var node=new Object();
node.color="red"
node.father=null;
node.left=null;
node.right=null;
node.key=key;
node.val=val;
return node;
},
queue:function(){ //自己写的一个队列,先进先出
var q=new Object();
q.lists=[];
q.length=0;
q.push_back=function(node){
//console.log(this)
this.lists.push(node);
this.length=this.length+1;
};
q.front=function(){
return this.lists[0];
}
q.pop_front=function(){
this.lists.shift();
this.length=this.length-1;
}
return q;
},
root:null,
uncle:function(pnode){//获取节点的叔叔节点
if(!pnode.father.father)return null;
if(pnode.father==pnode.father.father.left){
return pnode.father.father.right;
}
return pnode.father.father.left;
},
leftRotate:function(x,y){
//var x=pnode;
//var y=pnode.right;
// console.log(x)
// console.log(y)
x.right=y.left;
if(y.left!=null){
y.left.father=x;
}
y.father=x.father;
if(x==this.root){ //x为根时的处理
this.root=y;
}else{
if(x==x.father.left){
x.father.left=y;
}else{
x.father.right=y;
}
}
y.left=x;
x.father=y;
},
rightRotate:function(x,y){
//var x=pnode;
//var y=pnode.left;
x.left=y.right;
if(y.right!=null){
y.right.father=x; //更换那个在xy中间的数的父亲从y变成x
}
y.father=x.father;
if(x==this.root){
this.root=y;
}else{
if(x.father.left==x){
x.father.left=y;
}else{
x.father.right=y;
}
}
y.right=x;
x.father=y;
},
adjust:function(pnode){ //调整节点
console.log("adjust:"+pnode.key)
if(!pnode)return;
if(pnode==this.root){
pnode.color="black";
return;
}
if(pnode.father&&pnode.father.color=="black"){
return;
}
if(pnode.father && pnode.father.color=="red"){
if(this.uncle(pnode)&&this.uncle(pnode).color=="red"){
//如果叔叔和父亲都是红色
console.log("都是red")
this.uncle(pnode).color="black";
pnode.father.color="black";
pnode.father.father.color="red";
console.log(pnode.father)
console.log(this.uncle(pnode))
this.adjust(pnode.father.father);
return;
}
if(!this.uncle(pnode) || this.uncle(pnode).color=="black"){
//如果叔叔节点为空或者为黑
if(pnode==pnode.father.left){
if(pnode.father==pnode.father.father.left){
//LL
console.log("ll")
var color=pnode.father.color;
pnode.father.color=pnode.father.father.color;
pnode.father.father.color=color;
this.rightRotate(pnode.father.father,pnode.father);
}
else{
//LR
console.log("lr")
var father=pnode.father;
this.rightRotate(pnode.father,pnode);
this.adjust(father);
}
}else{
if(pnode.father==pnode.father.father.left){
//RL
console.log("rl")
var father=pnode.father;
this.leftRotate(pnode.father,pnode);
this.adjust(father);
}
else{
//RR
console.log("rr")
var color=pnode.father.color;
pnode.father.color=pnode.father.father.color;
pnode.father.father.color=color;
//console.log(pnode)
this.leftRotate(pnode.father.father,pnode.father);
}
}
}
}
},
insert:function(key,val){ //插入
console.log("insert:"+key)
if(this.root==null){
this.root=this.node(key,val); //根节点的颜色为黑色
this.root.color="black";
//console.log(this.root)
return;
}
var p=this.root;
while(1){
if(p.key==key){ //如果key相同，则更新值
p.val=val;
return;
}
if(key>p.key){
if(p.right==null){
p.right=this.node(key,val);
p.right.father=p;
this.adjust(p.right)
return;
}
p=p.right;
}
else{
if(p.left==null){
p.left=this.node(key,val);
p.left.father=p;
this.adjust(p.left);
return;
}
p=p.left;
}
}
},
show:function(){
//层先法显示红黑树
queue=this.queue(); //新建一个队列
queue.push_back(this.root);
var i=0;
while(queue.length!=0){
//console.log(1);
var node=queue.front();
queue.pop_front();
if(node==null){console.log("nil"+i);i=i+1;continue;}
console.log(node.color+" "+node.key+":"+node.val);
queue.push_back(node.left);
queue.push_back(node.right);
}
}
}
var rbtree;
rbtree.insert(12,"aaa");
rbtree.insert(1,"aaa");
rbtree.insert(9,"aaa");
rbtree.insert(2,"aaa");
rbtree.insert(0,"aaa");
rbtree.insert(11,"aaa");
rbtree.insert(7,"aaa");
rbtree.insert(19,"aaa");
rbtree.insert(4,"aaa");
rbtree.insert(15,"aaa");
rbtree.insert(18,"aaa");
rbtree.insert(5,"aaa");
rbtree.insert(14,"aaa");
rbtree.insert(13,"aaa");
rbtree.insert(10,"aaa");
rbtree.insert(16,"aaa");
rbtree.insert(6,"aaa");
rbtree.insert(3,"aaa");
rbtree.insert(8,"aaa");
rbtree.insert(17,"aaa");/**/
rbtree.show();
</script>
因篇幅问题不能全部显示，请点此查看更多更全内容