平衡二叉树AVL

程序员文章站 2022-03-05 12:56:54

...

1.概述:

为什么引入平衡二叉树？二叉排序树（BST）存在问题：已经排序过的数组，例如{1,2,3,4,5}，转化为二叉排序树时，其实就是一个单链表，完全没有二叉排序树的优势，甚至查找的时候比单链表还要慢（需要判断左子树）

平衡二叉树(AVL树)：对BST的升级，它是一颗空树，或者左、右子树高度差的绝对值不能超过1，并且左右两颗子树也都是平衡二叉树。在一棵具有N 个节点的树中，我们希望该树的高度能够维持在logN左右，插入和查找效率都能保证在对数的时间复杂度内完成。

实现方法：红黑树、AVL、替罪羊树、Treap、伸展树等。

平衡二叉树的缺点：每次增删之后，都要进行平衡，会降低效率

2.实现思路:

1.左旋转：

如果BST的右子树高度-左子树高度>1，左旋转：

用当前根节点的值，创建新节点
将新节点的左子树设置为根节点的左子树
将新节点的右子树设置为根节点右子树的左子树
把根节点的值替换为其右子树的值
把根节点的右子树设置为其右子树的右子树。
把根节点的左子节点设置为新节点

2.右旋转：

如果BST的左子树高度-右子树高度>1，右旋转：与左旋转相反

用当前根节点的值，创建新节点
将新节点的右子树设置为根节点的右子树
将新节点的左子树设置为根节点左子树的右子树
把根节点的值替换为其左子树的值
把根节点的左子树设置为其左子树的左子树。
把根节点的右子节点设置为新节点

3.双旋转：

左子树高于右子树,但是左子树的右子树高度，大于左子树的左子树的高度(靠内的子树的高度高)，那么先对左子树做左旋转，然后根节点进行右旋转
右子树高于左子树,但是右子树的左子树高度，大于右子树的右子树的高度(靠内的子树的高度高)，那么先对右子树做右旋转，然后根节点进行左旋转

3.代码实现：

首先必须实现以下方法：

计算树的高度方法
计算左子树的高度的方法
计算右子树的高度的方法
左旋方法
右旋方法

在对BST树进行增删之后，要立即判断树的左右子树的高度，如果不满足平衡二叉树的要求，则根据情况进行左旋转、右旋转或者双旋转

具体代码如下:

package com.bruce.binarytree;

/**
 * 二叉排序树（BST）存在问题：已经排序过的数组，例如{1,2,3,4,5}，转化为二叉排序树时，其实就是一个单链表，完全没有二叉排序树的优势，甚至查找的时候比单链表还要慢（需要判断左子树）
 * 平衡二叉树(AVL树)：对BST的升级？？？ 它是一颗空树，或者左右子树高度差的绝对值不能超过1，并且左右两颗子树也都是平衡二叉树。
 * 实现方法：红黑树、AVL、替罪羊树、Treap、伸展树等。
 * 缺点：每次增删之后，都要进行平衡，会降低效率
 * @author bwang018
 *
 */
public class AVLBinaryTree {

	public static void main(String[] args) {
	    // TODO Auto-generated method stub
	    //1.右子树高于左子树，左旋转
//	    int [] array = {4,3,6,5,7,8};
		
	    //2.左子树高于右子树，右旋转
//	    int [] array = {10,12,8,9,7,6};
		
	    //3.双旋转：左子树高于右子树,但是左子树的右子树高度，大于左子树的左子树的高度(靠内的子树的高度高)，那么先对左子树做左旋转
	    int [] array = {10,11,7,6,8,9};
		
	    //4.双旋转：右子树高于左子树,但是右子树的左子树高度，大于右子树的右子树的高度(靠内的子树的高度高)，那么先对右子树做右旋转
//	    int [] array = {2,1,6,5,7,3};
		
	    AVLTree avlTree = new AVLTree();
	    for (int i = 0; i < array.length; i++) {
	        avlTree.add(new AVLNode(array[i]));
	    }
	    //中序遍历AVL树
	    System.out.println("中序遍历......");
	    avlTree.infixOrder();
	    
	    System.out.println("平衡处理......");
	    System.out.println("树的高度=" + avlTree.root.height());
	    System.out.println("树的左子树高度=" + avlTree.root.leftHeight());
	    System.out.println("树的右子树高度=" + avlTree.root.rightHeight());
	    System.out.println("当前的根节点" + avlTree.root);
	    System.out.println("根节点的左子节点" + avlTree.root.leftNode);
	    System.out.println("根节点的右子节点" + avlTree.root.rightNode);
	}

}

class AVLTree{
	AVLNode root;
	public void add(AVLNode node){
		if (root == null) {
			root = node;
		}else {
			root.add(node);
		}
	}
	
	//将非AVL树转为AVL树
	public void rightRotate(){
		int leftHeight = root.leftHeight();
		int rightHeight = root.rightHeight();
		if (Math.abs(leftHeight - rightHeight) > 1) {
			root.leftRotate();
		}
	}
	
	//中序遍历
	public void infixOrder(){
		if (root == null) {
			System.out.println("二叉树为空，不能遍历");
			return;
		}
		root.infixOrder();
	}
	
}
class AVLNode{
	public int value;
	public AVLNode leftNode;
	public AVLNode rightNode;
	
	
	public AVLNode(int value) {
		super();
		this.value = value;
	}
	
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public AVLNode getLeftNode() {
		return leftNode;
	}
	public void setLeftNode(AVLNode leftNode) {
		this.leftNode = leftNode;
	}
	public AVLNode getRightNode() {
		return rightNode;
	}
	public void setRightNode(AVLNode rightNode) {
		this.rightNode = rightNode;
	}
	
	public void add(AVLNode node){
		if (node == null) {
			return;
		}
		if (node.value < this.value) {
			if (null == this.leftNode) {
				this.leftNode = node;
			}else {
				//递归地向左子树添加
				this.leftNode.add(node);
			}
		}else {
			if (null == this.rightNode) {
				this.rightNode = node;
			}else {
				//递归地向右子树添加
				this.rightNode.add(node);
			}
		}
		//当添加节点完成后，如果右子树的高度比左子树的高度 > 1，那么需要左旋转
		if (rightHeight() - leftHeight() > 1) {
			//如果右子树的左子树高度，大于右子树的右子树的高度，那么先对右子树做右旋转
			if (rightNode != null && rightNode.leftHeight() > rightNode.rightHeight()) {
				//对左子树做左旋转
				rightNode.rightRotate();
			}
			leftRotate();
			return;
		}
		//当添加节点完成后，如果左子树的高度比右子树的高度 > 1，那么需要右旋转
		if (leftHeight() - rightHeight() > 1) {
			//如果左子树的右子树高度，大于左子树的左子树的高度，那么先对左子树做左旋转
			if (leftNode != null && leftNode.rightHeight() > leftNode.leftHeight()) {
				//对左子树做左旋转
				leftNode.leftRotate();
			}
			rightRotate();
		}
	}
	
	//中序遍历
	public void infixOrder(){
		if (this.leftNode != null) {
			this.leftNode.infixOrder();
		}
		System.out.println(this);
		if (this.rightNode != null) {
			this.rightNode.infixOrder();
		}
	}
	
	//查找要删除的节点
	public AVLNode search(int value){
		if (this.value == value) {
			return this;
		}else if (this.value > value) {
			if (this.leftNode == null) {
				return null;
			}else {
				return this.leftNode.search(value);
			}
		}else {
			if (this.rightNode == null) {
				return null;
			}else {
				return this.rightNode.search(value);
			}
		}
	}
	
	//查找要删除节点的父节点
	public AVLNode searchParent(int value){
		//如果当前节点就是要删除节点的父节点，直接返回this
		if ((this.leftNode != null && this.leftNode.value == value) || (this.rightNode != null && this.rightNode.value == value)) {
			return this;
		}else {
			if (this.value > value && this.leftNode != null) {
				return this.leftNode.searchParent(value);
			}else if(this.value <= value && this.rightNode != null){ //防止有相同的值不能被遍历到，这里要用=
				return this.rightNode.searchParent(value);
			}else {
				return null;
			}
		}
	}
	
	//以当前节点为根节点，计算树的高度
	public int height(){
		return Math.max(leftNode == null ? 0:leftNode.height(), rightNode == null ? 0: rightNode.height()) + 1;
	}
	
	//当前节点左子树的高度
	public int leftHeight(){
		if (leftNode == null) {
			return 0;
		}
		return leftNode.height();
	}
	
	//当前节点右子树的高度
	public int rightHeight(){
		if (rightNode == null) {
			return 0;
		}
		return rightNode.height();
	}
	
	//AVL 左旋转方法: 右子树高度-左子树高度 > 1
	public void leftRotate(){
		//用当前根节点的值，创建新节点
		AVLNode newAvlNode = new AVLNode(value);
		//将新节点的左子树设置为根节点的左子树
		if (leftNode != null) {
			newAvlNode.leftNode = leftNode;
		}
		//把新节点的右子树设置为根节点右子树的左子树
		if (rightNode != null && rightNode.leftNode != null) {
			newAvlNode.rightNode = rightNode.leftNode;
		}
		if (rightNode != null) {
			//把根节点的值替换为其右子节点的值
			value = rightNode.value;
			//把根节点的右子树设置为其右子树的右子树。
			rightNode = rightNode.rightNode;
		}
		//把根节点的左子节点设置为新节点
		leftNode = newAvlNode;
		
	}
	
	//AVL 右旋转方法: 左子树高度-右子树高度 > 1
	public void rightRotate(){
		//用当前根节点的值，创建新节点
		AVLNode newAvlNode = new AVLNode(value);
		//将新节点的右子树设置为根节点的右子树
		if (rightNode != null) {
			newAvlNode.rightNode = rightNode;
		}
		//把新节点的左子树设置为根节点左子树的右子树
		if (leftNode != null && leftNode.rightNode != null) {
			newAvlNode.leftNode = leftNode.rightNode;
		}
		if (rightNode != null) {
			//把根节点的值替换为其左子树的值
			value = leftNode.value;
			//把根节点的左子树设置为其左子树的左子树。
			leftNode = leftNode.leftNode;
		}
		//把根节点的右子节点设置为新节点
		rightNode = newAvlNode;
		
	}
	
	@Override
	public String toString() {
		return "AVLNode [value=" + value + "]";
	}
}

相关标签：数据结构与算法数据结构与算法

上一篇： Xml序列化的图文代码详解

下一篇： xml学习（7） .net 获取xml节点或者属性最大值

平衡二叉树AVL

1.概述:

2.实现思路:

1.左旋转：

2.右旋转：

3.双旋转：

3.代码实现：

PHP码农平衡性

算法学习笔记二叉树和图遍历—深搜 DFS 与广搜 BFS

【树】B051_LC_二叉树中所有距离为 K 的结点（广搜 + 深搜存储父节点）

翻转二叉树

平衡二叉搜索树及其java实现

[PHP] 算法-二叉树的子结构判断的PHP实现

教你通过B+Tree平衡多叉树理解InnoDB引擎的聚集和非聚集索引

二、服务器优化（1）负载平衡

PHP ClassObject -- PHP 自排序二叉树的深入解析

C二叉树基础

平衡二叉树AVL

1.概述:

2.实现思路:

1.左旋转：

2.右旋转：

3.双旋转：

3.代码实现：

PHP码农平衡性

算法学习笔记 二叉树和图遍历—深搜 DFS 与广搜 BFS

【树】B051_LC_二叉树中所有距离为 K 的结点（广搜 + 深搜存储父节点）

翻转二叉树

平衡二叉搜索树及其java实现

[PHP] 算法-二叉树的子结构判断的PHP实现

教你通过B+Tree平衡多叉树理解InnoDB引擎的聚集和非聚集索引

二、服务器优化（1）负载平衡

PHP ClassObject -- PHP 自排序二叉树的深入解析

C二叉树基础

算法学习笔记二叉树和图遍历—深搜 DFS 与广搜 BFS