邊排序邊平衡
//二叉排序樹
function BtreeNode(data) {
this.data = data;
this.bf = 0;
}
BtreeNode.prototype.setL = function(node){
this.lchild = node;
}
BtreeNode.prototype.setR = function(node){
this.rchild = node;
}
BtreeNode.prototype.search = function(key){
if(key == this.data){
return {find:true,node:this};
}else if(key < this.data){
if(!this.lchild){
return {find:false,node:this};
}
return this.lchild.search(key);
}else{
if(!this.rchild){
return {find:false,node:this};
}
return this.rchild.search(key);
}
}
BtreeNode.prototype.insert = function(key){
var searchResult = this.search(key);
if(!searchResult.find){
var s = new BtreeNode(key);
if(key<searchResult.node.data){
searchResult.node.lchild = new BtreeNode(key);
}else{
searchResult.node.rchild = new BtreeNode(key);
}
return true;
}
return false;
}
BtreeNode.prototype.delete = function(){
if(!this.rchild){
var p = this;
p = this.lchild;
}else if(!this.lchild){
var p = this
p = this.rchild;
}else{
var q = this;
var s = this.rchild;
while(s.rchild){
q = s;
s = s.rchild;
}
this.data = s.data;
if(q!=this){
q.rchild = s.lchild;
}else{
q.lchild = s.lchild;
}
}
}
BtreeNode.prototype.deleteKey = function(key){
if(this.data == key){
this.delete();
}else if(this.data>key){
this.lchild.deleteKey(key);
}else{
this.rchild.deleteKey(key);
}
}
//計算深度
function GetBtreeLength(t){
var l = 0,r = 0;
if(!t){
return 0;
}
else if(!t.lchild&&!t.rchild){
return 1;
}
else{
if(t.lchild){
l = GetBtreeLength(t.lchild);
}
if(t.rchild){
r = GetBtreeLength(t.rchild);
}
return l>r?l+1:r+1;
}
}
BtreeNode.prototype.setBF = function(){
if(!this){
return;
}
var l = GetBtreeLength(this.lchild);
var r = GetBtreeLength(this.rchild);
this.bf = r-l;
if(this.lchild){
this.lchild.setBF();
}
if(this.rchild){
this.rchild.setBF();
}
}
//右旋
BtreeNode.prototype.rightRotate = function(){
var l = this.lchild;
this.lchild = l.rchild;
var t = deepCopy(this);
l.rchild = t;
this.data = l.data;
this.bf = l.bf;
this.lchild = l.lchild;
this.rchild = l.rchild;
}
//左旋
var deepCopy= function(source) {
var result={};
for (var key in source) {
result[key] = typeof source[key]==='object'?
deepCopy(source[key]): source[key];
}
return result;
}
BtreeNode.prototype.leftRotate = function(){
var l = this.rchild;
this.rchild = l.lchild;
var t = deepCopy(this);
l.lchild = t;
this.data = l.data;
this.bf = l.bf;
this.lchild = l.lchild;
this.rchild = l.rchild;
}
//左旋轉(zhuǎn)平衡
BtreeNode.prototype.leftBalance = function(){
var l = this.lchild,lr;
switch (l.bf){
case 1:
this.bf = l.bf = 0;
this.rightRotate();
break;
case -1:
lr = l.rchild;
switch (lr.bf){
case 1:
this.bf = -1;
l.bf = 0;
break;
case 0:
this.bf = l.bf = 0;
break;
case -1:
this.bf = 0;
l.bf = 1;
break;
}
lr.bf = 0;
this.lchild.leftRotate();
this.rightRotate();
}
}
//右旋轉(zhuǎn)平衡
BtreeNode.prototype.rightBalance = function(){
var l = this.rchild,lr;
switch (l.bf){
case -1:
this.bf = l.bf = 0;
this.leftRotate();
break;
case 1:
lr = l.lchild;
switch (lr.bf){
case 1:
this.bf = 1;
l.bf = 0;
break;
case 0:
this.bf = l.bf = 0;
break;
case -1:
this.bf = 0;
l.bf = -1;
break;
}
lr.bf = 0;
this.rchild.rightRotate();
this.leftRotate();
}
}
//插入并平衡二叉樹
var taller = false;
BtreeNode.prototype.insertAVL = function(e){
if(e.data == this.data){
console.info('數(shù)值已經(jīng)存在,無法插入')
taller = false;
return false;
}
if(e.data < this.data){
if(!this.lchild){
this.lchild = e;
this.lchild.bf = 0;
taller = true;
console.info('在'+this.data+'的左子樹添加一個節(jié)點'+e.data);
}
else{
if(!this.lchild.insertAVL(e)){
return false;
}
}
if(taller){
console.info('節(jié)點是'+this.data+',平衡因子是'+this.bf);
switch (this.bf){
case 1:
this.leftBalance();
console.info('對節(jié)點左平衡處理');
taller = false;
break;
case 0:
this.bf = 1;
console.info('變更節(jié)點'+this.data+'的平衡因子為1');
taller = true;
break;
case -1:
this.bf = 0;
console.info('變更節(jié)點'+this.data+'的平衡因子為0');
taller = false;
break;
}
}
}
else{
if(!this.rchild){
this.rchild = e;
this.rchild.bf = 0;
taller = true;
console.info('在'+this.data+'的右子樹添加一個節(jié)點'+e.data);
}else{
if(!this.rchild.insertAVL(e)){
return false;
}
}
if(taller){
console.info('節(jié)點是'+this.data+',平衡因子是'+this.bf);
switch(this.bf){
case 1:
this.bf = 0;
console.info('變更節(jié)點'+this.data+'的平衡因子為0');
taller = false;
break;
case 0:
this.bf = -1;
console.info('變更節(jié)點'+this.data+'的平衡因子為-1');
taller = true;
break;
case -1:
this.rightBalance();
console.info('對節(jié)點右平衡處理');
taller = false;
break;
}
}
}
return true;
}
var b = new BtreeNode(0);
b.insertAVL(new BtreeNode(1)).btree;
b.insertAVL(new BtreeNode(2)).btree;
b.insertAVL(new BtreeNode(3)).btree;
b.insertAVL(new BtreeNode(4)).btree;
b.insertAVL(new BtreeNode(5)).btree;
b.insertAVL(new BtreeNode(6)).btree;
b.insertAVL(new BtreeNode(7)).btree;
b.insertAVL(new BtreeNode(8)).btree;
b.insertAVL(new BtreeNode(9)).btree;
b.insertAVL(new BtreeNode(10)).btree;
b.insertAVL(new BtreeNode(11)).btree;
console.info(b);
output
在0的右子樹添加一個節(jié)點1
節(jié)點是0,平衡因子是0
變更節(jié)點0的平衡因子為-1
在1的右子樹添加一個節(jié)點2
節(jié)點是1,平衡因子是0
變更節(jié)點1的平衡因子為-1
節(jié)點是0,平衡因子是-1
對節(jié)點右平衡處理
在2的右子樹添加一個節(jié)點3
節(jié)點是2,平衡因子是0
變更節(jié)點2的平衡因子為-1
節(jié)點是1,平衡因子是0
變更節(jié)點1的平衡因子為-1
在3的右子樹添加一個節(jié)點4
節(jié)點是3,平衡因子是0
變更節(jié)點3的平衡因子為-1
節(jié)點是2,平衡因子是-1
對節(jié)點右平衡處理
在4的右子樹添加一個節(jié)點5
節(jié)點是4,平衡因子是0
變更節(jié)點4的平衡因子為-1
節(jié)點是3,平衡因子是0
變更節(jié)點3的平衡因子為-1
節(jié)點是1,平衡因子是-1
對節(jié)點右平衡處理
在5的右子樹添加一個節(jié)點6
節(jié)點是5,平衡因子是0
變更節(jié)點5的平衡因子為-1
節(jié)點是4,平衡因子是-1
對節(jié)點右平衡處理
在6的右子樹添加一個節(jié)點7
節(jié)點是6,平衡因子是0
變更節(jié)點6的平衡因子為-1
節(jié)點是5,平衡因子是0
變更節(jié)點5的平衡因子為-1
節(jié)點是3,平衡因子是0
變更節(jié)點3的平衡因子為-1
在7的右子樹添加一個節(jié)點8
節(jié)點是7,平衡因子是0
變更節(jié)點7的平衡因子為-1
節(jié)點是6,平衡因子是-1
對節(jié)點右平衡處理
在8的右子樹添加一個節(jié)點9
節(jié)點是8,平衡因子是0
變更節(jié)點8的平衡因子為-1
節(jié)點是7,平衡因子是0
變更節(jié)點7的平衡因子為-1
節(jié)點是5,平衡因子是-1
對節(jié)點右平衡處理
在9的右子樹添加一個節(jié)點10
節(jié)點是9,平衡因子是0
變更節(jié)點9的平衡因子為-1
節(jié)點是8,平衡因子是-1
對節(jié)點右平衡處理
在10的右子樹添加一個節(jié)點11
節(jié)點是10,平衡因子是0
變更節(jié)點10的平衡因子為-1
節(jié)點是9,平衡因子是0
變更節(jié)點9的平衡因子為-1
節(jié)點是7,平衡因子是0
變更節(jié)點7的平衡因子為-1
節(jié)點是3,平衡因子是-1
對節(jié)點右平衡處理
BtreeNode {
data: 7,
bf: 0,
rchild:
BtreeNode {
data: 9,
bf: -1,
rchild: BtreeNode { data: 10, bf: -1, rchild: [Object] },
lchild:
{ data: 8,
bf: 0,
rchild: undefined,
setL: [Function],
setR: [Function],
search: [Function],
insert: [Function],
delete: [Function],
deleteKey: [Function],
setBF: [Function],
rightRotate: [Function],
leftRotate: [Function],
leftBalance: [Function],
rightBalance: [Function],
insertAVL: [Function] } },
lchild:
{ data: 3,
bf: 0,
rchild:
{ data: 5,
bf: 0,
rchild: [Object],
lchild: [Object],
setL: [Function],
setR: [Function],
search: [Function],
insert: [Function],
delete: [Function],
deleteKey: [Function],
setBF: [Function],
rightRotate: [Function],
leftRotate: [Function],
leftBalance: [Function],
rightBalance: [Function],
insertAVL: [Function] },
lchild:
{ data: 1,
bf: 0,
rchild: [Object],
lchild: [Object],
setL: [Function],
setR: [Function],
search: [Function],
insert: [Function],
delete: [Function],
deleteKey: [Function],
setBF: [Function],
rightRotate: [Function],
leftRotate: [Function],
leftBalance: [Function],
rightBalance: [Function],
insertAVL: [Function] },
setL: [Function],
setR: [Function],
search: [Function],
insert: [Function],
delete: [Function],
deleteKey: [Function],
setBF: [Function],
rightRotate: [Function],
leftRotate: [Function],
leftBalance: [Function],
rightBalance: [Function],
insertAVL: [Function] } }
[Finished in 0.1s]
