signed

QiShunwang

“诚信为本、客户至上”

数据结构与算法-平衡二叉树(AVL树)

2020/8/20 13:22:48   来源:

平衡二叉树(AVL树)

基本介绍

  1. 平衡二叉树也叫平衡二叉搜索树,又被称为AVL树,可以保证查询效率较高
  2. 具有以下特点
    (1)它是一颗空树或他的左右两个子树的高度差额绝对值不差过1
    (2)它的左右两颗子树都是一颗平衡二叉树
    在这里插入图片描述
    平衡二叉树的旋转
    1. 左旋转
      Node newNode = new Node(value);

      //把新的节点的左子树设置成当前的左子树
      newNode.left = left;

      //把新的节点的右子树设置成当前节点右子树的左子树
      newNode.right = right.left;

      //把当前节点的值替换成右子树的值
      value = right.value;

      //把当前节点的右子树设置成当前节点的右子树的右子树
      right = right.right;

      //把当前节点的左子树设置为新节点
      left = newNode;

    2. 右旋转
      Node newNode = new Node(value);

      //把新的节点右子树设置成当前节点的右子树
      newNode.right = right;

      //把新的节点的左子树设置成当前节点左子树的右子树
      newNode.left = left.right;

      //把当前节点的值替换成左子树的值
      value = left.value;

      //把当前节点的左子树设置成当前节点左子树的左子树
      left = left.left;

      //把当前节点的右子树设置为新节点
      right = newNode;

    3. 双旋转
      (1) 当符合右旋转条件时
      它的左子树的右子树的高度大于它的左子树高度时
      先对这个节点的左子节点左旋转
      再对当前节点进行右旋转即可
      (2) 符合左旋转条件时
      如果他的右子树高度大于左子树时
      先对这个节点的右节点右旋转
      再对当前节点左旋转即可

代码实现

public class AVLTreeDemo {
	
	public static void main(String[] args) {
		
		//int[] arr = {4, 3, 6, 5, 7, 8};
		//int[] arr = {10, 12, 8, 9, 7, 6};
		int[] arr = {10, 11, 7, 6, 8, 9};
		AVLTree tree = new AVLTree();
		for (int value : arr) {
			tree.add(new Node(value));
		}
		
		Node root = tree.getRoot();
		
		tree.infixOrder();
		System.out.println("avl高度:" + root.height());
		System.out.println("avl左子树高度:" + root.leftHeight());
		System.out.println("avl右子树高度:" + root.rightHeight());
		
	}
	
}
class AVLTree {
	
	Node root;

	public AVLTree() {
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void add(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}
	
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
		} else {
			System.out.println("二叉平衡树为空,不能遍历");
		}
	}
	
}

class Node {
	
	int value;
	
	Node left;
	
	Node right;

	public Node(int value) {
		this.value = value;
	}
	
	//左旋转
	private void leftRotate() {
		Node newNode = new Node(value);
		
		//把新的节点的左子树设置成当前的左子树
		newNode.left = left;
		
		//把新的节点的右子树设置成当前节点右子树的左子树
		newNode.right = right.left;
		
		//把当前节点的值替换成右子树的值
		value = right.value;
		
		//把当前节点的右子树设置成当前节点的右子树的右子树
		right = right.right;
		
		//把当前节点的左子树设置为新节点
		left = newNode;
	}
	
	//右旋转
	private void rightRotate() {
		Node newNode = new Node(value);
		
		//把新的节点右子树设置成当前节点的右子树
		newNode.right = right;
		
		//把新的节点的左子树设置成当前节点左子树的右子树
		newNode.left = left.right;
		
		//把当前节点的值替换成左子树的值
		value = left.value;
		
		//把当前节点的左子树设置成当前节点左子树的左子树
		left = left.left;
		
		//把当前节点的右子树设置为新节点
		right = newNode;
	}
		
	//返回以该节点为根节点的树的高度
	public int height() {
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
	}
	
	//返回左子树的高度
	public int leftHeight() {
		if (left == null) {
			return 0;
		}
		return left.height();
	}
	
	//返回右子树的高度
	public int rightHeight() {
		if (right == null) {
			return 0;
		}
		return right.height();
	}
	
	//添加节点
	public void add(Node node) {
		//递归形式添加节点,需要满足二叉排序树的要求
		if (node == null) {
			return;
		}
		
		//判断传入节点的值和当前节点的值进行比较
		if (node.value < this.value) {
			if (this.left == null) {
				this.left = node;
			} else {
				this.left.add(node);
			}
		} else {
			if (this.right == null) {
				this.right = node;
			} else {
				this.right.add(node);
			}
		}
		
		//当添加完一个节点后,设置为avl树
		if (rightHeight() - leftHeight() > 1) {
			if (right.leftHeight() > right.rightHeight()) {
				right.rightRotate();
			}
			leftRotate();  // 左旋转
		} else if (leftHeight() - rightHeight() > 1) {
			if (left.rightHeight() > left.leftHeight()) {
				left.leftRotate();
			}
			rightRotate();
		}
	}
	
	public void infixOrder() {
		
		if (this.left != null) {
			this.left.infixOrder();
		}
		
		System.out.println(this);
		
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}
}