JavaScript數(shù)據(jù)結(jié)構(gòu)25—AVL平衡二叉樹(shù)算法

邊排序邊平衡

//二叉排序樹(shù)
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);
  }
}
//計(jì)算深度
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();
  }
}
//插入并平衡二叉樹(shù)
var taller = false;
BtreeNode.prototype.insertAVL = function(e){
  if(e.data == this.data){
    console.info('數(shù)值已經(jīng)存在,無(wú)法插入')
    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+'的左子樹(shù)添加一個(gè)節(jié)點(diǎn)'+e.data);
    }
    else{
      if(!this.lchild.insertAVL(e)){
        return false;
      }
    }
    if(taller){
      console.info('節(jié)點(diǎn)是'+this.data+',平衡因子是'+this.bf);
      switch (this.bf){
        case 1:
          this.leftBalance();
          console.info('對(duì)節(jié)點(diǎn)左平衡處理');
          taller = false;
          break;
        case 0:
          this.bf = 1;
          console.info('變更節(jié)點(diǎn)'+this.data+'的平衡因子為1');
          taller = true;
          break;
        case -1:
          this.bf = 0;
          console.info('變更節(jié)點(diǎn)'+this.data+'的平衡因子為0');
          taller = false;
          break;
      }
    }
  }
  else{
    if(!this.rchild){
      this.rchild = e;
      this.rchild.bf = 0;
      taller = true;
      console.info('在'+this.data+'的右子樹(shù)添加一個(gè)節(jié)點(diǎn)'+e.data);
    }else{
      if(!this.rchild.insertAVL(e)){
        return false;
      }
    }
    if(taller){
      console.info('節(jié)點(diǎn)是'+this.data+',平衡因子是'+this.bf);
      switch(this.bf){
        case 1:
          this.bf = 0;
          console.info('變更節(jié)點(diǎn)'+this.data+'的平衡因子為0');
          taller = false;
          break;
        case 0:
          this.bf = -1;
          console.info('變更節(jié)點(diǎn)'+this.data+'的平衡因子為-1');
          taller = true;
          break;
        case -1:
          this.rightBalance();
          console.info('對(duì)節(jié)點(diǎn)右平衡處理');
          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的右子樹(shù)添加一個(gè)節(jié)點(diǎn)1
節(jié)點(diǎn)是0,平衡因子是0
變更節(jié)點(diǎn)0的平衡因子為-1
在1的右子樹(shù)添加一個(gè)節(jié)點(diǎn)2
節(jié)點(diǎn)是1,平衡因子是0
變更節(jié)點(diǎn)1的平衡因子為-1
節(jié)點(diǎn)是0,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在2的右子樹(shù)添加一個(gè)節(jié)點(diǎn)3
節(jié)點(diǎn)是2,平衡因子是0
變更節(jié)點(diǎn)2的平衡因子為-1
節(jié)點(diǎn)是1,平衡因子是0
變更節(jié)點(diǎn)1的平衡因子為-1
在3的右子樹(shù)添加一個(gè)節(jié)點(diǎn)4
節(jié)點(diǎn)是3,平衡因子是0
變更節(jié)點(diǎn)3的平衡因子為-1
節(jié)點(diǎn)是2,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在4的右子樹(shù)添加一個(gè)節(jié)點(diǎn)5
節(jié)點(diǎn)是4,平衡因子是0
變更節(jié)點(diǎn)4的平衡因子為-1
節(jié)點(diǎn)是3,平衡因子是0
變更節(jié)點(diǎn)3的平衡因子為-1
節(jié)點(diǎn)是1,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在5的右子樹(shù)添加一個(gè)節(jié)點(diǎn)6
節(jié)點(diǎn)是5,平衡因子是0
變更節(jié)點(diǎn)5的平衡因子為-1
節(jié)點(diǎn)是4,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在6的右子樹(shù)添加一個(gè)節(jié)點(diǎn)7
節(jié)點(diǎn)是6,平衡因子是0
變更節(jié)點(diǎn)6的平衡因子為-1
節(jié)點(diǎn)是5,平衡因子是0
變更節(jié)點(diǎn)5的平衡因子為-1
節(jié)點(diǎn)是3,平衡因子是0
變更節(jié)點(diǎn)3的平衡因子為-1
在7的右子樹(shù)添加一個(gè)節(jié)點(diǎn)8
節(jié)點(diǎn)是7,平衡因子是0
變更節(jié)點(diǎn)7的平衡因子為-1
節(jié)點(diǎn)是6,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在8的右子樹(shù)添加一個(gè)節(jié)點(diǎn)9
節(jié)點(diǎn)是8,平衡因子是0
變更節(jié)點(diǎn)8的平衡因子為-1
節(jié)點(diǎn)是7,平衡因子是0
變更節(jié)點(diǎn)7的平衡因子為-1
節(jié)點(diǎn)是5,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在9的右子樹(shù)添加一個(gè)節(jié)點(diǎn)10
節(jié)點(diǎn)是9,平衡因子是0
變更節(jié)點(diǎn)9的平衡因子為-1
節(jié)點(diǎn)是8,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
在10的右子樹(shù)添加一個(gè)節(jié)點(diǎn)11
節(jié)點(diǎn)是10,平衡因子是0
變更節(jié)點(diǎn)10的平衡因子為-1
節(jié)點(diǎn)是9,平衡因子是0
變更節(jié)點(diǎn)9的平衡因子為-1
節(jié)點(diǎn)是7,平衡因子是0
變更節(jié)點(diǎn)7的平衡因子為-1
節(jié)點(diǎn)是3,平衡因子是-1
對(duì)節(jié)點(diǎn)右平衡處理
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]

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容