devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

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

作者：小惠珠哦 | 2024-07-21 22:43:56

赞

踩

java中的平衡树

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

 

目录

相关概念

二叉平衡树平衡原理

相关代码

完整代码

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

  1. 相关概念

    1. 树的高度：

      某结点的高度是指从该结点到叶子结点的最长简单路径边的条数。（从1开始计数，当然你也可以从0开始，咋舒服砸来，这里我从1开始）。

    2. BF因子：

      将二叉树上结点的左子树高度减去右子树高度的值称为平衡银子BF。

    3. 二叉排序树：

      又称为二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树：

      若它的左子树不空，则左子树上所有结点的值均小于它的跟结点的值；

      若它的右子树不空，则右子树上所有结点的值均大于它的跟结点的值；

      它的左，右子树也分别为二叉排序树。

    4. 二叉平衡树：

      是一种二叉排序树，其中每一个接待你的左子树和右子树的高度差至多等于1。

  2. 二叉平衡树平衡原理 

    1. 举个栗子：

      图1：为平衡二叉树，其中每个结点的BF的绝对值都至多为1，所以图1为平衡二叉树。

      图2：不是平衡二叉树，其中值为5的结点，其左子树的高度为2，右子树的高度为0，所以其BF为2，所以图2不是平衡二叉树。

    2. 实现原理

      1、首先，按照二叉排序树的结构将结点插入二叉树种。

      2、每当插入一个新的结点后，判断此时二叉树是否平衡。

      3、若平衡则返回其二叉树的根结点，表示当前结点添加成功。

      4、若不平衡，则构建平衡二叉树：

             1、此时二叉树为不平衡

             2、找出此时二叉树的最小不平衡结点

             3、根据不平衡情况旋转子树，构建平衡，如下图：

      （对应上图）

      对下面两个位置进行解释：

      第一个位置：表示最小不平衡结点的BF值，若大于0表示该结点的左子树的高度大于其右子树的高度，用左表示，反之则用右表示。

      第二个位置：表示最小不平衡结点的孩子结点的BF值，若最小不平衡结点的BF>0,则表示其左孩子的BF值，反之则表示其右孩子的BF值。同第一个位置，BF>0使用左表示，反之用右表示。

      1、左左：如第一棵树。最小不平衡结点为6，其BF值为2，大于0。计算其左孩子的BF值，其左孩子的BF值为1，大于0。所以使用左左表示。这种情况下，将以最小不平衡结点为根的子树向右旋转，使其左孩子最为根节点（不一定是整棵树的根节点，只是这个子树的根结点），将最小不平衡结点及其右子树添加到新树种（这里的新树是以结点3为跟的树）（在添加不平衡结点及其右子树的过程中若又出现不平衡，则继续判断）。旋转过程如下。旋转后树达到平衡。

      2、左右：如第二棵树。最小不平衡结点为6，其BF=2,其左孩子的BF=-1，此时在使用情况1中的方法构建平衡，会变成第三棵树的情况，任然是不平衡的。在这种情况下，需要先对最小不平衡结点的左子树向左旋转，使整棵树变成情况1中左左的情况，此时再将最小不平衡结点向右旋转，过程如下图。完成构建平衡。

      3、右左：同情况2的左右，只是此时需先将以最小不平衡结点的右孩子为根的子树向右旋转，此时达到情况4右右的，再将以最小不平衡结点为根的子树向左旋转即可构建平衡。图略。

      4、右右：同情况1的左左，只是此时向左旋转。图略。

  3. 相关代码

    获取某结点高度

    1.     /**
    2. 	 * 获得树的高度（从1开始）
    3. 	 * 
    4. 	 * @param root
    5. 	 * @return
    6. 	 */
    7. 	public int getDepth(TreeNode root) {
    8. 		// 递归计算某结点的最大高度
    9. 		if (root == null) {
    10. 			return 0;
    11. 		}
    12. 		int leftDepth = 1;
    13. 		int rightDepth = 1;
    14. 		leftDepth += getDepth(root.left);
    15. 		rightDepth += getDepth(root.right);
    16. 		if (leftDepth > rightDepth) {
    17. 			return leftDepth;
    18. 		} else {
    19. 			return rightDepth;
    20. 		}
    21. 	}

    获取最小不平衡子树

    1.     /**
    2. 	 * 获得最小不平衡树的根结点
    3. 	 * 
    4. 	 * @param root
    5. 	 *            整棵树的根
    6. 	 * @return 最小不平衡结点
    7. 	 */
    8. 	public TreeNode getMinNoBalanceNode(TreeNode root) {
    9. 		// 临时结点，用于遍历
    10. 		TreeNode temp = root;
    11. 		// 记录最小不平衡结点
    12. 		TreeNode noBalanceNode = null;
    13. 		// 是否开始寻找最小不平衡结点
    14. 		// 第一种情况，从根结点开始就发生不平衡
    15. 		// 第二种情况，从某一结点开始发生不平衡
    16. 		// 原理：从第一个不平衡结点开始，记录不平衡结点，直至某个结点为平衡结点时，
    17. 		// noBalanceNode指向的接待你即为最小不平衡结点。
    18. 		boolean isFind = false;
    19. 		int bf = 0;
    20. 		while (root != null) {
    21. 			// 计算某结点的BF
    22. 			bf = getDepth(temp.left) - getDepth(temp.right);
    23. 			if (bf == 0 || bf == -1 || bf == 1) {
    24. 				if (isFind) {
    25. 					break;
    26. 				}
    27. 				if (bf > 0) {
    28. 					temp = temp.left;
    29. 				} else {
    30. 					temp = temp.right;
    31. 				}
    32. 			} else {
    33. 				isFind = true;
    34. 				noBalanceNode = temp;
    35. 				if (bf > 0) {
    36. 					temp = temp.left;
    37. 				} else {
    38. 					temp = temp.right;
    39. 				}
    40. 			}
    41. 		}
    42. 		// 返回最小不平衡结点
    43. 		return noBalanceNode;
    44. 	}

    判断树是否平衡

    1.     /**
    2. 	 * 判断二叉树是否平衡
    3. 	 * 类似二叉树层次遍历实现方法，遍历所有结点，计算其BF，判断该结点是否平衡
    4. 	 * @param root
    5. 	 *            根结点
    6. 	 * @return 是否平衡
    7. 	 */
    8. 	public boolean isBalance(TreeNode root) {
    9. 		// 存储结点
    10. 		LinkedList<TreeNode> nodes = new LinkedList<>();
    11. 		// 若果结点为空则平衡
    12. 		if (root == null) {
    13. 			return true;
    14. 		}
    15. 		int leftDepth = 0;
    16. 		int rightDepth = 0;
    17. 		nodes.add(root);
    18. 		// 遍历树，判断是否平衡
    19. 		while (!nodes.isEmpty()) {
    20. 			root = nodes.poll();
    21. 			leftDepth = getDepth(root.left);
    22. 			rightDepth = getDepth(root.right);
    23. 			if ((leftDepth - rightDepth) == 0 || (leftDepth - rightDepth) == 1 || (leftDepth - rightDepth) == -1) {
    24. 				if (root.left != null) {
    25. 					nodes.add(root.left);
    26. 				}
    27. 				if (root.right != null) {
    28. 					nodes.add(root.right);
    29. 				}
    30. 			} else {
    31. 				return false;
    32. 			}
    33. 		}
    34. 		return true;
    35. 	}

    结点插入代码

    1. /**
    2. 	 * 添加结点 向二叉平衡术中添加结点， 将结点添加到对应位置后， 检查此时树是否平衡， 若不平衡则构建平衡树。
    3. 	 * 
    4. 	 * @param root
    5. 	 *            二叉平衡术根结点
    6. 	 * @param newNode
    7. 	 *            新增结点
    8. 	 * @return 整棵树的根结点
    9. 	 */
    10. 	public TreeNode addNodeToTree(TreeNode root, TreeNode newNode) {
    11. 		// 若根结点为空，则新增结点最为根结点
    12. 		if (root == null) {
    13. 			return newNode;
    14. 		}
    15. 		// 临时结点，遍历用
    16. 		TreeNode temp = root;
    17. 		// 记录新增结点的父结点
    18. 		TreeNode parent = root;
    19. 		// 记录新增结点在是其父结点的最孩子还是右孩子
    20. 		boolean isLeft = true;
    21. 		// 遍历二叉树，将新结点插入
    22. 		while (temp != null) {
    23. 			parent = temp;
    24. 			if (temp.val > newNode.val) {
    25. 				temp = temp.left;
    26. 				isLeft = true;
    27. 			} else if (temp.val < newNode.val) {
    28. 				temp = temp.right;
    29. 				isLeft = false;
    30. 			} else {
    31. 				return root;
    32. 			}
    33. 		}
    34. 		// 插入新结点
    35. 		if (isLeft) {
    36. 			parent.left = newNode;
    37. 		} else {
    38. 			parent.right = newNode;
    39. 		}
    40. 		// 判断插入新结点后的，此时二叉树是否平衡
    41. 		if (isBalance(root)) {
    42. 			return root;
    43. 		}
    44. 		// 返回平衡后树的根结点
    45. 		return balance(root);
    46. 	}

    构建平衡

    1.     /**
    2. 	 * 构建平衡 将二叉树构建平衡 共4种不平衡情况。
    3. 	 * 
    4. 	 * @param root
    5. 	 *            根结点
    6. 	 * @return 整棵树的根结点
    7. 	 */
    8. 	public TreeNode balance(TreeNode root) {
    9. 		// 获取最小不平衡结点
    10. 		TreeNode noBalanceNode = getMinNoBalanceNode(root);
    11. 		// bf因子
    12. 		int bf = 0;
    13. 		// 计算最小不平衡结点BF
    14. 		bf = getDepth(noBalanceNode.left) - getDepth(noBalanceNode.right);
    15. 		if (bf > 0) {// 最小不平衡结点BF>0即其左子树高度大于右子树高度
    16. 			// 计算最小不平衡结点左子树的BF
    17. 			bf = getDepth(noBalanceNode.left.left) - getDepth(noBalanceNode.left.right);
    18. 			if (bf > 0) {// 第一种不平衡情况
    19. 				root = right(root, noBalanceNode);
    20. 			} else {// 第二种不平衡情况
    21. 				left(root, noBalanceNode.left);
    22. 				root = right(root, noBalanceNode);
    23. 			}
    24. 		} else {
    25. 			bf = getDepth(noBalanceNode.right.left) - getDepth(noBalanceNode.right.right);
    26. 			if (bf > 0) {// 第三种不平衡情况
    27. 				right(root, noBalanceNode.left);
    28. 				root = left(root, noBalanceNode);
    29. 			} else {// 第四种不平衡情况
    30. 				root = left(root, noBalanceNode);
    31. 			}
    32. 		}
    33. 		// 返回平衡后的根结点
    34. 		return root;
    35. 	}

    左旋

    1. 	/**
    2. 	 * 向左旋转二叉树
    3. 	 * 
    4. 	 * @param root
    5. 	 *            二叉树的根结点
    6. 	 * @param noBalanceNode
    7. 	 *            不平衡结点
    8. 	 * @return 树的根结点
    9. 	 */
    10. 	public TreeNode left(TreeNode root, TreeNode noBalanceNode) {
    11. 		if (root.val == noBalanceNode.val) { // 最小不平衡结点为根结点
    12. 			// 记录新的根结点
    13. 			root = noBalanceNode.right;
    14. 			// 置空最小不平衡结点的右子树
    15. 			noBalanceNode.right = null;
    16. 			// 将以最小不平衡结点为根的二叉树，添加到新根的二叉树中
    17. 			addNodeToTree(root, noBalanceNode);
    18. 		} else {// 最小不平衡结点不为根结点
    19. 			// 获取最小不平衡结点的父结点
    20. 			TreeNode parent = getParent(root, noBalanceNode);
    21. 			// 根据二叉排序树，判断最小不平衡结点是父结点的左孩子还是右孩子
    22. 			boolean isleft = parent.val > noBalanceNode.val ? true : false;
    23. 			if (isleft) {
    24. 				// 左转最小不平衡结点，并将旋转后根结点设置为父结点的左孩子，旋转完成
    25. 				parent.left = left(noBalanceNode, noBalanceNode);
    26. 			} else {
    27. 				parent.right = left(noBalanceNode, noBalanceNode);
    28. 			}
    29. 		}
    30. 		return root;
    31. 	}

     

    右旋

    1. 	/**
    2. 	 * 向右旋转二叉树
    3. 	 * 
    4. 	 * @param root
    5. 	 *            根结点
    6. 	 * @param noBalanceNode
    7. 	 *            最小不平衡结点
    8. 	 * @return 树的根结点
    9. 	 */
    10. 	public TreeNode right(TreeNode root, TreeNode noBalanceNode) {
    11. 		TreeNode tempNode = null;
    12. 		if (root.val == noBalanceNode.val) {
    13. 			root = noBalanceNode.left;
    14. 			noBalanceNode.left = null;
    15. 			addNodeToTree(root, noBalanceNode);
    16. 		} else {
    17. 			TreeNode parent = getParent(root, noBalanceNode);
    18. 			boolean isleft = parent.val > noBalanceNode.val ? true : false;
    19. 			if (isleft) {
    20. 				parent.left = right(noBalanceNode, noBalanceNode);
    21. 			} else {
    22. 				parent.right = right(noBalanceNode, noBalanceNode);
    23. 			}
    24. 		}
    25. 		return root;
    26. 	}

     

  4. 完整代码

https://download.csdn.net/download/biglxl/11258926

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/862452
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号