AVLTree简单实现

今天突然感觉AVL树在Tree这种数据结构中有比较重要的作用，特别是理解如何将不平衡的树转化为平衡树的左旋和右旋操作是理解和学习AVL树的基础。

先上代码：

//定义树的基本节点
const Node = function(item){
	//基本元素
	this.item = item;
 	//节点的高度
 	this.height = 1;
	this.left = null;
	this.right = null;
}
const AVLTree = function(){
	//定义树的根节点
	let root = null;
	this.height = (Node)=>{
		if (Node == null){
			return 0;
 		}
		return Node.height;
	}
	this.rightRotate = (y)=>{
		
		let x = y.left;
		let T2 = x.right;
		x.right = y;
 		y.left = T2;
		y.height = Math.max(this.height(y.left), this.height(y.right))+1;
		x.height = Math.max(this.height(x.left), this.height(x.right))+1;
		return x;
	}
	this.leftRotate = (x)=> {
        let y = x.right;
        let T2 = y.left;
        y.left = x;
        x.right = T2;
        y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
        x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
        return y;
    }
 	this.getBalanceFactor = (Node)=>{
    	if (Node == null) {
            return 0;
        }
        return this.height(Node.left) - this.height(Node.right);
    }
	const insertNodeHelper = (node, item)=>{
    	//three case 
    	//根节点为空
    	if (node == null) {
      		return new Node(item);
    	}
    	//搜索需要插入的位置
    	if (item < node.item) {
      	//插入左子树
      		node.left = insertNodeHelper(node.left, item);
    	} else if (item > node.item) {
      		node.right = insertNodeHelper(node.right, item);
    	} else {
      	//这里返回是处理递归的结束
      		return node;
    	}
    	//处理插入的情况
    	node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    	let balanceFactor  = this.getBalanceFactor(node);
    	if (balanceFactor > 1) {
      		if (item < node.left.item) {//说明是插入左子树的左子树导致不平衡，因此需要右旋
        		return this.rightRotate(node);
      		} else if (item > node.left.item) {//说明是插入左子树的右子树导致不平衡，需要先左旋，再右旋
        		node.left = this.leftRotate(node.left);
        		return this.rightRotate(node);
      		}
    	} 
    	if (balanceFactor < -1) {
      		if (item > node.right.item) {
        		return this.leftRotate(node);
      		} else if (item < node.right.item) {
        		node.right = this.rightRotate(node.right);
       			return this.leftRotate(node);
     		}
    	}

    	return node;
  	}

  	this.insertNode = (item) => {
    	// console.log(root);
    	root = insertNodeHelper(root, item);
  	}

  	const deleteNodeHelper = (root, item)=>{
    	if (root == null){
      		return root;
    	}
    	if (item < root.item) {
      		root.left =  deleteNodeHelper(root.left, item);
    	} else if (item > root.item) {
      		root.right = deleteNodeHelper(root.right, item);
    	} else {
      		//只有一个节点
      		if(root.left == null || root.right == null) {
        		let temp = null;
        		if (temp == root.left) {
          			temp = root.right;
        		} else {
          			temp = root.left;
        		}
        		if (temp == null) {
          		//全部左右子节点为空
          			temp = root;
          			root = null;
          		//根节点为空
        		} else{
          		//根节点赋值为temp子节点
          			root = temp;
        		}
      		} else {
        		// 获取右子树最小的节点
        		let temp  = this.nodeWithMimumValue(root.right);
        		root.item = temp.item;
        		root.right = deleteNodeHelper(root.right, temp.item);
      		}
    	}
    	if (root == null) {
      		return root;
    	}

    	root.height = Math.max(this.height(root.left), this.height(root.right)) + 1;
    	let balanceFactor = this.getBalanceFactor(root);
    	if (balanceFactor > 1) {
     	 	if (this.getBalanceFactor(root.left) >=0) {
        		//右旋
        		return this.rightRotate(root);
      		} else {
        		root.left = this.leftRotate(root.left);
        		return this.rightRotate(root);
      		}
    	} 
    	if (balanceFactor < -1) {
      		if (this.getBalanceFactor(root.right) <= 0) {
        		//左旋
        		return this.leftRotate(root);
      		} else {
        		root.right = this.rightRotate(root.right);
        		return this.leftRotate(root);
      		}
    	}
    	return root;
  	}
 	this.deleteNode = (item) => {
    	// console.log(root);
    	root = deleteNodeHelper(root, item);
  	}

  	this.nodeWithMimumValue = (node) => {
    	let current = node;
    	while (current.left !== null){
      		current = current.left;
    	}
    	return current;
  	}

  	this.preOrder = () => {
    	preOrderHelper(root);
  	}
  
  	const preOrderHelper = (node) => {
    	if (node) {
      		console.log(node.item);
      		preOrderHelper(node.left);
      		preOrderHelper(node.right);
    	}
  	}
}

let tree = new AVLTree();
tree.insertNode(33);
tree.insertNode(13);
tree.insertNode(53);
tree.insertNode(9);
tree.insertNode(21);
tree.insertNode(61);
tree.insertNode(8);
tree.insertNode(11);
tree.preOrder();
tree.deleteNode(13);
console.log("After Deletion: ");
tree.preOrder();

平衡二叉树的代码主要包括插入和删除两个基本操作，而这两个基本操作最关键的是理解左旋和右旋。关于左旋和右旋的知识，我们以后再慢慢分享。