平衡二叉树（AVL树）算法 Java实现

阅读量：2432 次

发布时间：2019-05-10

本文共 11518 字，大约阅读时间需要 38 分钟。

定义：

平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree），是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF（balance Factor）。那么平衡二叉树上所有结点的平衡因子只可能是-1,0和1.

距离插入结点最近的，且平衡因子的绝对值大于1的结点为跟的子树，我们称之为最小不平衡子树。

算法分析：

递归法插入结点后，如果检测到某个结点的左子树或右子树“长高”了而导致这棵树不平衡，那么就需要对其进行左平衡或右平衡，此结点就是最小不平衡子树的根节点

在左平衡或右平衡时，当最小不平衡子树根节点的平衡因子是大于1时，就右旋，小于-1时就左旋；最小不平衡子树的BF与它对应子树（右旋时要对应左子树，左旋时对应右子树）的BF 符号（正负）相反时，就需要对子树先进行一次反向旋转以使得符号相同后，再旋转不平衡子树根节点才能够完成平衡操作。

示例图片：

P:最小不平衡子树的根节点

L:P左子树的根节点

LR:L右子树的根节点

N：新插入的结点

插入时的左平衡右平衡

左平衡（即右旋最小不平衡子树）

一.BF符号相同（PL都为正）：

情况一：

操作：无论N是LL的左子树还是右子树，直接右旋P

BF结果：P:0;L:0

情况二：

操作：右旋P

BF结果：P:0;L:0

二.BF符号不同（PL一正一负）

情况一：N在LR的左子树，LR 的BF 值为 1

操作：先左旋L，再右旋P

BF结果：P:-1; L:0; LR:0

情况二：N是LR，LR的BF值为0

操作：先左旋L，再右旋P

BF结果：P:0; L:0; LR(N):0

情况三：N在LR的右子树，LR的 BF 值为 -1

操作：先左旋L，再右旋P

BF结果：P:0; L:1; LR:0

右平衡（即左旋最小不平衡子树）

和左平衡道理一样，BF符号相同不相同的情况图在最下。

删除时的左平衡右平衡

删除的左平衡和右平衡包含插入时的所有情况，结合图可以轻易理解，但是删除有特殊情况，插入时不可能会出现的。

特殊情况为：

左平衡 L 结点 BF为0

操作：右旋P

BF结果：P:1 L:-1

注意：这种删除的特殊情况左平衡后，树并没有变矮，而其他情况全部会变矮

右平衡也相同道理，见图

代码：

import java.util.Random;import java.util.concurrent.ConcurrentLinkedQueue;public class AVLTree {		/** 根结点 */	private TreeNode rootNode;		/** 插入时判断是否变高 */	private boolean taller;		/** 删除时判断是否变矮*/	private boolean lower;		/**	 * 插入	 * @param key	 * @return	 */	public boolean insertAVL(int key) {		if (this.rootNode == null) {			rootNode = new TreeNode(key, 0);			return true;		}				return insertAVL(key, this.rootNode, null, null);			}		public boolean insertAVL(int key,			TreeNode node, TreeNode parentNode, Boolean leftOrRight) {				//插入新结点，树“长高”，至taller为true		if (node == null) {			node = new TreeNode(key, 0);						if (leftOrRight) {				parentNode.setLchild(node);			} else {				parentNode.setRchild(node);			}			//第一层必须判断长高没有，所以必须为true			taller = true;			// 插入了新结点返回true ，没有返回false			return true;		}				// 树中已存在和e有相同关键字的结点则不再插入		if (key == node.getData()) {			taller = false;			return false;		}				// 小于则再左子树中继续搜索		if (key < node.getData()) {			// 插入了新结点返回true ，没有返回false			if (!insertAVL(key, node.getLchild(), node, true))				return false;						if (taller) {				switch (node.getBf()) {				case 1:					leftBalance(node);					taller = false;					break;				case 0:					node.setBf(1);					taller = true;					break;				case -1:					node.setBf(0);					taller = false;					break;				}			}		// 大于则在右子树中继续查找		} else {			if (!insertAVL(key, node.getRchild(), node, false))				return false;						if (taller) {				switch (node.getBf()) {				case 1:					node.setBf(0);					taller = false;					break;				case 0:					node.setBf(-1);					taller = true;					break;				case -1:					rightBalance(node);					taller = false;					break;				}			}		}				return true;	}		/**	 * 删除结点	 * @param key	 * @return	 */	public boolean removeAVL(int key) {		if (this.rootNode == null) {			return false;		}				return removeAVL(key, this.rootNode, null, null);	}		public boolean removeAVL(int key,			TreeNode node, TreeNode parentNode, Boolean leftOrRight) {				//没有找到要删除的结点		if (node == null) {			return false;		}				//找到要删除的结点		if (key == node.getData()) {						//要删除的结点 左右子树都不为空			if (node.getLchild() != null && node.getRchild() != null) {								// 删除前驱结点，将前驱结点的值放入当前结点处				TreeNode precursorNode = precursorNode(node);				removeAVL(precursorNode.getData(), node.getLchild(), node, true);								// 替换				// 必须在旋转之前，不然就会替换错目标				node.setData(precursorNode.getData());								// 前驱必定是在左子树中				if (lower) {					switch (node.getBf()) {					case 1:						node.setBf(0);						lower = true;						break;					case 0:						node.setBf(-1);						lower = false;						break;					case -1:						// 当出现删除时独有的情况（rchild bf 0）经过平衡后 并没有变矮						if (node.getRchild().getBf() == 0)							lower = false;						else 							lower = true;												rightBalance(node);						break;					}				}								return true;							// 左子树为空、右子树为空或者两者都为空			} else {								// 根结点（特殊情况）				if (parentNode == null) {					rootNode = node.getLchild() == null ? node.getRchild() : node.getLchild();					return true;				}								if (leftOrRight) {					parentNode.setLchild(							node.getLchild() == null ? node.getRchild() : node.getLchild());				} else {					parentNode.setRchild(							node.getLchild() == null ? node.getRchild() : node.getLchild());				}								//删除结点后 树变低了				lower = true;				return true;			}		}				// 继续在左子树或右子树中查找		if (key < node.getData()) {			if (!removeAVL(key, node.getLchild(), node, true))				return false;						// 注意:删除后变低的情况和插入变高的情况完全相反，			// 如删除后进行平衡旋转实际上整体变低一层。结合图理解			if (lower) {				switch (node.getBf()) {				case 1:					node.setBf(0);					lower = true;					break;				case 0:					node.setBf(-1);					lower = false;					break;				case -1:					// 当出现删除时独有的情况（rchild bf 0）经过平衡后 并没有变矮					if (node.getRchild().getBf() == 0)						lower = false;					else 						lower = true;										rightBalance(node);					break;				}			}					} else {			if (!removeAVL(key, node.getRchild(), node, false))				return false;						if (lower) {				switch (node.getBf()) {				case 1:					// 当出现删除时独有的情况（lchild bf 0）经过平衡后 并没有变矮					if (node.getLchild().getBf() == 0)						lower = false;					else						lower = true;										leftBalance(node);					break;				case 0:					node.setBf(1);					lower = false;					break;				case -1:					node.setBf(0);					lower = true;					break;				}			}		}						return true;	}		/**	 * 找前驱	 * @param node	 * @return	 */	private TreeNode precursorNode(TreeNode node) {		if (node == null)			return null;				TreeNode precursorNode = node.getLchild();		while (precursorNode != null) {			if (precursorNode.getRchild() != null)				precursorNode = precursorNode.getRchild();			else				break;		}				return precursorNode;	}		/**	 * 对以node为根的二叉排序树做右旋处理 	 * 处理之后node 为新的树根结点，即旋转处理之前的左子树的根结点	 */	public void rightRotate(TreeNode node) {		TreeNode leftNode = node.getLchild();		TreeNode rightNode = node.getRchild();				TreeNode rootNode = new TreeNode(node.getData(), node.getBf());		rootNode.setLchild(leftNode);		rootNode.setRchild(rightNode);				node.setData(leftNode.getData());		node.setBf(leftNode.getBf());		node.setLchild(leftNode.getLchild());		node.setRchild(rootNode);				rootNode.setLchild(leftNode.getRchild());	}		/**	 * 对以node 为根的二叉排序树做左旋处理
	 * 处理之后node 为新的树根结点，即旋转处理之前的右子树的根结点 	 */	public void leftRotate(TreeNode node) {		TreeNode leftNode = node.getLchild();		TreeNode rightNode = node.getRchild();				TreeNode rootNode = new TreeNode(node.getData(), node.getBf());		rootNode.setLchild(leftNode);		rootNode.setRchild(rightNode);				node.setData(rightNode.getData());		node.setBf(rightNode.getBf());		node.setLchild(rootNode);		node.setRchild(rightNode.getRchild());				rootNode.setRchild(rightNode.getLchild());	}		/**	 * 对以 node结点为根的二叉树作左平衡旋转处理
	 * 以node为根结点的树就是最小不平衡二叉树，且左子树的高度大于右子树，平衡因子大于1	 */	public void leftBalance(TreeNode node) {		TreeNode leftNode = node.getLchild();				switch (leftNode.getBf()) {		// 左结点和node结点平衡因子符号相同，直接右旋最小不平衡树		case 1:			leftNode.setBf(0);			node.setBf(0);			rightRotate(node);			break;		// 左结点和node结点平衡因子符号不同，先左旋左孩子，再右旋最小不平衡树		case -1:			TreeNode leftNodeRchild = leftNode.getRchild();						switch (leftNodeRchild.getBf()) {			case 1:				node.setBf(-1);				leftNode.setBf(0);				break;			case 0:				node.setBf(0);				leftNode.setBf(0);				break;			case -1:				node.setBf(0);				leftNode.setBf(1);				break;			}						leftNodeRchild.setBf(0);						leftRotate(leftNode);			rightRotate(node);			break;		//主要用于删除。插入时不可能会有这种情况		//并且平衡后树的高度并没有变矮，而其他两种情况树会变矮		case 0:			node.setBf(1);			leftNode.setBf(-1);			rightRotate(node);			break;		}	}		public void rightBalance(TreeNode node) {		TreeNode rightNode = node.getRchild();				switch (rightNode.getBf()) {		case -1:			node.setBf(0);			rightNode.setBf(0);			leftRotate(node);			break;		case 1:			TreeNode rightNodeLchild = rightNode.getLchild();			switch (rightNodeLchild.getBf()) {			case 1:				node.setBf(0);				rightNode.setBf(-1);				break;			case 0:				node.setBf(0);				rightNode.setBf(0);				break;			case -1:				node.setBf(1);				rightNode.setBf(0);				break;			}						rightNodeLchild.setBf(0);						rightRotate(rightNode);			leftRotate(node);			break;		//主要用于删除。插入时不可能会有这种情况		//并且平衡后树的高度并没有变矮，而其他两种情况树会变矮		case 0:			node.setBf(-1);			rightNode.setBf(1);			leftRotate(node);			break;		}	}		/**	 * 打印树	 */	public void printTree() {		ConcurrentLinkedQueue
    
      queue = new ConcurrentLinkedQueue<>();		ConcurrentLinkedQueue
     
       tempQueue = new ConcurrentLinkedQueue<>();		queue.add(this.rootNode);		int offset = 0;		int counter = 2;		for (int i = 0; i < 50; i++)			System.out.print(" ");		while (queue.peek() != null) {			TreeNode node = queue.poll();						// 找 node的parentNode begin			TreeNode parentNode = null;			TreeNode searchNode = this.rootNode;			int key = node.getData();						while (true) {				if (key < searchNode.getData()) {					parentNode = searchNode;					searchNode = searchNode.getLchild();				} else if (key > searchNode.getData()){					parentNode = searchNode;					searchNode = searchNode.getRchild();				} else {					break;				}			}						// --- end 									String side = "L";			if (parentNode != null && parentNode.getRchild() == node)				side = "R";			System.out.print(node.getData() + "(" + (parentNode == null ? "" : parentNode.getData()) + " " + side + ")");			if (parentNode != null && parentNode.getRchild() != node)				for (int i = 0; i < counter; i++)					System.out.print(" ");			if (node.getLchild() != null)				tempQueue.add(node.getLchild());			if (node.getRchild() != null)				tempQueue.add(node.getRchild());			if (queue.isEmpty()) {				offset += 3;				// counter--;				copyQueue(tempQueue, queue);				System.out.println();				for (int i = 0; i < 50 - offset; i++)					System.out.print(" ");			}		}	}	private void copyQueue(ConcurrentLinkedQueue
      
        source, ConcurrentLinkedQueue
       
         target) {		while (source.peek() != null) {			target.add(source.poll());		}	}		public TreeNode getRootNode() {		return this.rootNode;	}		//中序遍历	public void inOrderTraverse(TreeNode node){        if(node != null){            // 左，根，右            inOrderTraverse(node.getLchild());            System.out.print(node.getData() + "  ");            inOrderTraverse(node.getRchild());        }    }		public static void main(String[] args) {		int[] arr = {3, 2, 1, 4, 5, 6, 7, 10, 9, 8};				AVLTree tree = new AVLTree();		for (int a : arr) {			tree.insertAVL(a);		}				tree.printTree();				System.out.println("\n----------------remove begin-----------------");				// 随机删除		for (int i = 0; i < 10; i++) {		    int index = new Random().nextInt(10) + 1;		    		    System.out.println("\n删除：" + index);		    tree.removeAVL(index);		    tree.inOrderTraverse(tree.getRootNode());		    		    System.out.println();		    tree.printTree();		}	}}/** * 二叉树结点 */class TreeNode {	private int data;		/** 结点的平衡因子  新增 */	private int bf;		private TreeNode lchild;		private TreeNode rchild;		public TreeNode(int data, int bf) {		super();		this.data = data;		this.bf = bf;	}	public int getData() {		return data;	}	public void setData(int data) {		this.data = data;	}	public int getBf() {		return bf;	}	public void setBf(int bf) {		this.bf = bf;	}	public TreeNode getLchild() {		return lchild;	}	public void setLchild(TreeNode lchild) {		this.lchild = lchild;	}	public TreeNode getRchild() {		return rchild;	}	public void setRchild(TreeNode rchild) {		this.rchild = rchild;	}	@Override	public String toString() {		return "TreeNode [data=" + data + ", bf=" + bf + ", lchild=" + lchild + ", rchild=" + rchild + "]";	}				}