JavaScript数据结构25—AVL平衡二叉树算法

边排序边平衡

//二叉排序树
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;
}
//左旋转平衡
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();
  }
}
//右旋转平衡
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('数值已经存在,无法插入')
    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+'的左子树添加一个节点'+e.data);
    }
    else{
      if(!this.lchild.insertAVL(e)){
        return false;
      }
    }
    if(taller){
      console.info('节点是'+this.data+',平衡因子是'+this.bf);
      switch (this.bf){
        case 1:
          this.leftBalance();
          console.info('对节点左平衡处理');
          taller = false;
          break;
        case 0:
          this.bf = 1;
          console.info('变更节点'+this.data+'的平衡因子为1');
          taller = true;
          break;
        case -1:
          this.bf = 0;
          console.info('变更节点'+this.data+'的平衡因子为0');
          taller = false;
          break;
      }
    }
  }
  else{
    if(!this.rchild){
      this.rchild = e;
      this.rchild.bf = 0;
      taller = true;
      console.info('在'+this.data+'的右子树添加一个节点'+e.data);
    }else{
      if(!this.rchild.insertAVL(e)){
        return false;
      }
    }
    if(taller){
      console.info('节点是'+this.data+',平衡因子是'+this.bf);
      switch(this.bf){
        case 1:
          this.bf = 0;
          console.info('变更节点'+this.data+'的平衡因子为0');
          taller = false;
          break;
        case 0:
          this.bf = -1;
          console.info('变更节点'+this.data+'的平衡因子为-1');
          taller = true;
          break;
        case -1:
          this.rightBalance();
          console.info('对节点右平衡处理');
          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的右子树添加一个节点1
节点是0,平衡因子是0
变更节点0的平衡因子为-1
在1的右子树添加一个节点2
节点是1,平衡因子是0
变更节点1的平衡因子为-1
节点是0,平衡因子是-1
对节点右平衡处理
在2的右子树添加一个节点3
节点是2,平衡因子是0
变更节点2的平衡因子为-1
节点是1,平衡因子是0
变更节点1的平衡因子为-1
在3的右子树添加一个节点4
节点是3,平衡因子是0
变更节点3的平衡因子为-1
节点是2,平衡因子是-1
对节点右平衡处理
在4的右子树添加一个节点5
节点是4,平衡因子是0
变更节点4的平衡因子为-1
节点是3,平衡因子是0
变更节点3的平衡因子为-1
节点是1,平衡因子是-1
对节点右平衡处理
在5的右子树添加一个节点6
节点是5,平衡因子是0
变更节点5的平衡因子为-1
节点是4,平衡因子是-1
对节点右平衡处理
在6的右子树添加一个节点7
节点是6,平衡因子是0
变更节点6的平衡因子为-1
节点是5,平衡因子是0
变更节点5的平衡因子为-1
节点是3,平衡因子是0
变更节点3的平衡因子为-1
在7的右子树添加一个节点8
节点是7,平衡因子是0
变更节点7的平衡因子为-1
节点是6,平衡因子是-1
对节点右平衡处理
在8的右子树添加一个节点9
节点是8,平衡因子是0
变更节点8的平衡因子为-1
节点是7,平衡因子是0
变更节点7的平衡因子为-1
节点是5,平衡因子是-1
对节点右平衡处理
在9的右子树添加一个节点10
节点是9,平衡因子是0
变更节点9的平衡因子为-1
节点是8,平衡因子是-1
对节点右平衡处理
在10的右子树添加一个节点11
节点是10,平衡因子是0
变更节点10的平衡因子为-1
节点是9,平衡因子是0
变更节点9的平衡因子为-1
节点是7,平衡因子是0
变更节点7的平衡因子为-1
节点是3,平衡因子是-1
对节点右平衡处理
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]