数据结构：二叉平衡树（AVL树）Java实现

╰半橙微兮° 2021-09-29 01:58 371阅读 0赞

# 二叉平衡树（AVL树）Java实现 #

**目录**

相关代码

完整代码

--------------------

（如有任何问题欢迎指出）

1.  # 相关概念 #
    
    1.  ### **树的高度：** ###
        
        > 某结点的高度是指从该结点到叶子结点的最长简单路径边的条数。（从1开始计数，当然你也可以从0开始，咋舒服砸来，这里我从1开始）。
    2.  ### **BF因子：** ###
        
        > 将二叉树上结点的左子树高度减去右子树高度的值称为平衡银子BF。
    3.  ### **二叉排序树：** ###
        
        > 又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：
        > 
        > 若它的左子树不空，则左子树上所有结点的值均小于它的跟结点的值；
        > 
        > 若它的右子树不空，则右子树上所有结点的值均大于它的跟结点的值；
        > 
        > 它的左，右子树也分别为二叉排序树。
    4.  ### **二叉平衡树：** ###
        
        > 是一种二叉排序树，其中每一个接待你的左子树和右子树的高度差至多等于1。
2.  # 二叉平衡树平衡原理  #
    
    1.  ### 举个栗子： ###
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70][]
        
        > 图1：为平衡二叉树，其中每个结点的BF的绝对值都至多为1，所以图1为平衡二叉树。
        > 
        > 图2：不是平衡二叉树，其中值为5的结点，其左子树的高度为2，右子树的高度为0，所以其BF为2，所以图2不是平衡二叉树。
    2.  ### 实现原理 ###
        
        > 1、首先，按照二叉排序树的结构将结点插入二叉树种。
        > 
        > 2、每当插入一个新的结点后，判断此时二叉树是否平衡。
        > 
        > 3、若平衡则返回其二叉树的根结点，表示当前结点添加成功。
        > 
        > 4、若不平衡，则构建平衡二叉树：
        > 
        >        1、此时二叉树为不平衡
        > 
        >        2、找出此时二叉树的最小不平衡结点
        > 
        >        3、根据不平衡情况旋转子树，构建平衡，如下图：
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 1][]
        
        > （对应上图）
        > 
        > 对下面两个位置进行解释：
        > 
        > 第一个位置：表示最小不平衡结点的BF值，若大于0表示该结点的左子树的高度大于其右子树的高度，用左表示，反之则用右表示。
        > 
        > 第二个位置：表示最小不平衡结点的孩子结点的BF值，若最小不平衡结点的BF>0,则表示其左孩子的BF值，反之则表示其右孩子的BF值。同第一个位置，BF>0使用左表示，反之用右表示。
        > 
        > 1、左左：如第一棵树。最小不平衡结点为6，其BF值为2，大于0。计算其左孩子的BF值，其左孩子的BF值为1，大于0。所以使用左左表示。这种情况下，将以最小不平衡结点为根的子树向右旋转，使其左孩子最为根节点（不一定是整棵树的根节点，只是这个子树的根结点），将最小不平衡结点及其右子树添加到新树种（这里的新树是以结点3为跟的树）（在添加不平衡结点及其右子树的过程中若又出现不平衡，则继续判断）。旋转过程如下。旋转后树达到平衡。
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 2][]
        
        > 2、左右：如第二棵树。最小不平衡结点为6，其BF=2,其左孩子的BF=-1，此时在使用情况1中的方法构建平衡，会变成第三棵树的情况，任然是不平衡的。在这种情况下，需要先对最小不平衡结点的左子树向左旋转，使整棵树变成情况1中左左的情况，此时再将最小不平衡结点向右旋转，过程如下图。完成构建平衡。
        
        ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 3][]
        
        > 3、右左：同情况2的左右，只是此时需先将以最小不平衡结点的右孩子为根的子树向右旋转，此时达到情况4右右的，再将以最小不平衡结点为根的子树向左旋转即可构建平衡。图略。
        > 
        > 4、右右：同情况1的左左，只是此时向左旋转。图略。
3.  # 相关代码 #
    
    > 获取某结点高度
    
        /**
        	 * 获得树的高度（从1开始）
        	 * 
        	 * @param root
        	 * @return
        	 */
        	public int getDepth(TreeNode root) {
        		// 递归计算某结点的最大高度
        		if (root == null) {
        			return 0;
        		}
        		int leftDepth = 1;
        		int rightDepth = 1;
        		leftDepth += getDepth(root.left);
        		rightDepth += getDepth(root.right);
        		if (leftDepth > rightDepth) {
        			return leftDepth;
        		} else {
        			return rightDepth;
        		}
        	}
    
    > 获取最小不平衡子树
    
        /**
        	 * 获得最小不平衡树的根结点
        	 * 
        	 * @param root
        	 *            整棵树的根
        	 * @return 最小不平衡结点
        	 */
        	public TreeNode getMinNoBalanceNode(TreeNode root) {
        		// 临时结点，用于遍历
        		TreeNode temp = root;
        		// 记录最小不平衡结点
        		TreeNode noBalanceNode = null;
        		// 是否开始寻找最小不平衡结点
        		// 第一种情况，从根结点开始就发生不平衡
        		// 第二种情况，从某一结点开始发生不平衡
        		// 原理：从第一个不平衡结点开始，记录不平衡结点，直至某个结点为平衡结点时，
        		// noBalanceNode指向的接待你即为最小不平衡结点。
        		boolean isFind = false;
        		int bf = 0;
        		while (root != null) {
        			// 计算某结点的BF
        			bf = getDepth(temp.left) - getDepth(temp.right);
        			if (bf == 0 || bf == -1 || bf == 1) {
        				if (isFind) {
        					break;
        				}
        				if (bf > 0) {
        					temp = temp.left;
        				} else {
        					temp = temp.right;
        				}
        			} else {
        				isFind = true;
        				noBalanceNode = temp;
        				if (bf > 0) {
        					temp = temp.left;
        				} else {
        					temp = temp.right;
        				}
        			}
        		}
        		// 返回最小不平衡结点
        		return noBalanceNode;
        	}
    
    > 判断树是否平衡
    
        /**
        	 * 判断二叉树是否平衡
        	 * 类似二叉树层次遍历实现方法，遍历所有结点，计算其BF，判断该结点是否平衡
        	 * @param root
        	 *            根结点
        	 * @return 是否平衡
        	 */
        	public boolean isBalance(TreeNode root) {
        		// 存储结点
        		LinkedList<TreeNode> nodes = new LinkedList<>();
        		// 若果结点为空则平衡
        		if (root == null) {
        			return true;
        		}
        		int leftDepth = 0;
        		int rightDepth = 0;
        		nodes.add(root);
        		// 遍历树，判断是否平衡
        		while (!nodes.isEmpty()) {
        			root = nodes.poll();
        			leftDepth = getDepth(root.left);
        			rightDepth = getDepth(root.right);
        			if ((leftDepth - rightDepth) == 0 || (leftDepth - rightDepth) == 1 || (leftDepth - rightDepth) == -1) {
        				if (root.left != null) {
        					nodes.add(root.left);
        				}
        				if (root.right != null) {
        					nodes.add(root.right);
        				}
        			} else {
        				return false;
        			}
        		}
        		return true;
        	}
    
    > 结点插入代码
    
        /**
        	 * 添加结点 向二叉平衡术中添加结点， 将结点添加到对应位置后， 检查此时树是否平衡， 若不平衡则构建平衡树。
        	 * 
        	 * @param root
        	 *            二叉平衡术根结点
        	 * @param newNode
        	 *            新增结点
        	 * @return 整棵树的根结点
        	 */
        	public TreeNode addNodeToTree(TreeNode root, TreeNode newNode) {
        		// 若根结点为空，则新增结点最为根结点
        		if (root == null) {
        			return newNode;
        		}
        		// 临时结点，遍历用
        		TreeNode temp = root;
        		// 记录新增结点的父结点
        		TreeNode parent = root;
        		// 记录新增结点在是其父结点的最孩子还是右孩子
        		boolean isLeft = true;
        		// 遍历二叉树，将新结点插入
        		while (temp != null) {
        			parent = temp;
        			if (temp.val > newNode.val) {
        				temp = temp.left;
        				isLeft = true;
        			} else if (temp.val < newNode.val) {
        				temp = temp.right;
        				isLeft = false;
        			} else {
        				return root;
        			}
        		}
        		// 插入新结点
        		if (isLeft) {
        			parent.left = newNode;
        		} else {
        			parent.right = newNode;
        		}
        		// 判断插入新结点后的，此时二叉树是否平衡
        		if (isBalance(root)) {
        			return root;
        		}
        		// 返回平衡后树的根结点
        		return balance(root);
        	}
    
    > 构建平衡
    
        /**
        	 * 构建平衡 将二叉树构建平衡 共4种不平衡情况。
        	 * 
        	 * @param root
        	 *            根结点
        	 * @return 整棵树的根结点
        	 */
        	public TreeNode balance(TreeNode root) {
        		// 获取最小不平衡结点
        		TreeNode noBalanceNode = getMinNoBalanceNode(root);
        		// bf因子
        		int bf = 0;
        		// 计算最小不平衡结点BF
        		bf = getDepth(noBalanceNode.left) - getDepth(noBalanceNode.right);
        		if (bf > 0) {// 最小不平衡结点BF>0即其左子树高度大于右子树高度
        			// 计算最小不平衡结点左子树的BF
        			bf = getDepth(noBalanceNode.left.left) - getDepth(noBalanceNode.left.right);
        			if (bf > 0) {// 第一种不平衡情况
        				root = right(root, noBalanceNode);
        			} else {// 第二种不平衡情况
        				left(root, noBalanceNode.left);
        				root = right(root, noBalanceNode);
        			}
        		} else {
        			bf = getDepth(noBalanceNode.right.left) - getDepth(noBalanceNode.right.right);
        			if (bf > 0) {// 第三种不平衡情况
        				right(root, noBalanceNode.left);
        				root = left(root, noBalanceNode);
        			} else {// 第四种不平衡情况
        				root = left(root, noBalanceNode);
        			}
        		}
        		// 返回平衡后的根结点
        		return root;
        	}
    
    > 左旋
    
        /**
        	 * 向左旋转二叉树
        	 * 
        	 * @param root
        	 *            二叉树的根结点
        	 * @param noBalanceNode
        	 *            不平衡结点
        	 * @return 树的根结点
        	 */
        	public TreeNode left(TreeNode root, TreeNode noBalanceNode) {
        		if (root.val == noBalanceNode.val) { // 最小不平衡结点为根结点
        			// 记录新的根结点
        			root = noBalanceNode.right;
        			// 置空最小不平衡结点的右子树
        			noBalanceNode.right = null;
        			// 将以最小不平衡结点为根的二叉树，添加到新根的二叉树中
        			addNodeToTree(root, noBalanceNode);
        		} else {// 最小不平衡结点不为根结点
        			// 获取最小不平衡结点的父结点
        			TreeNode parent = getParent(root, noBalanceNode);
        			// 根据二叉排序树，判断最小不平衡结点是父结点的左孩子还是右孩子
        			boolean isleft = parent.val > noBalanceNode.val ? true : false;
        			if (isleft) {
        				// 左转最小不平衡结点，并将旋转后根结点设置为父结点的左孩子，旋转完成
        				parent.left = left(noBalanceNode, noBalanceNode);
        			} else {
        				parent.right = left(noBalanceNode, noBalanceNode);
        			}
        		}
        		return root;
        	}
    
     
    
    > 右旋
    
        /**
        	 * 向右旋转二叉树
        	 * 
        	 * @param root
        	 *            根结点
        	 * @param noBalanceNode
        	 *            最小不平衡结点
        	 * @return 树的根结点
        	 */
        	public TreeNode right(TreeNode root, TreeNode noBalanceNode) {
        		TreeNode tempNode = null;
        		if (root.val == noBalanceNode.val) {
        			root = noBalanceNode.left;
        			noBalanceNode.left = null;
        			addNodeToTree(root, noBalanceNode);
        		} else {
        			TreeNode parent = getParent(root, noBalanceNode);
        			boolean isleft = parent.val > noBalanceNode.val ? true : false;
        			if (isleft) {
        				parent.left = right(noBalanceNode, noBalanceNode);
        			} else {
        				parent.right = right(noBalanceNode, noBalanceNode);
        			}
        		}
        		return root;
        	}
    
     
4.  # 完整代码 #

> [https://download.csdn.net/download/biglxl/11258926][https_download.csdn.net_download_biglxl_11258926]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70]: /images/20210920/2ab1196108a645b5b9cde8ce9c335e53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 1]: /images/20210920/69d92c85d45847a684dcf859637d90b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 2]: /images/20210920/bfe3dcbc0d0248568ca626729657ea33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JpZ2x4bA_size_16_color_FFFFFF_t_70 3]: /images/20210920/6f2f8a22ba8d4c72a5bcf338e1aa4f74.png
[https_download.csdn.net_download_biglxl_11258926]: https://download.csdn.net/download/biglxl/11258926