欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页  >  IT编程

平衡二叉树-java代码实现

程序员文章站 2022-03-10 21:30:15
资料引入说明平衡二叉树理论知识参考：https://blog.csdn.net/dengjili/article/details/111463328二叉排序树理论知识参考：https://blog.csdn.net/dengjili/article/details/111503799二叉排序树-java代码实现:https://blog.csdn.net/dengjili/article/details/111992147平衡二叉树是在二叉排序树代码基础上进行平衡的，这里直接使用了二...

资料引入说明

  • 平衡二叉树理论知识参考：https://blog.csdn.net/dengjili/article/details/111463328

  • 二叉排序树理论知识参考：https://blog.csdn.net/dengjili/article/details/111503799

  • 二叉排序树-java代码实现:https://blog.csdn.net/dengjili/article/details/111992147

平衡二叉树是在二叉排序树代码基础上进行平衡的，这里直接使用了二叉排序树代码，本章节重点在于讲解平衡的过程

代码说明

定义节点如下，增加平衡因子，结点高度，指向父结点的引用三个属性

public class AVLNode {
	private int value;
	private AVLNode leftNode;
	private AVLNode rightNode;
	private int balanceFactor;
	private int length;
	private AVLNode parentNode;
	// setter getter

采用层次遍历输出，便于观察使用，输出结点信息

public class AVLLevelTraversal {
	public static void traversal(AVLNode AVLNode) {
		System.out.println("----------------------");
		Queue<AVLNode> queue = new LinkedBlockingDeque<>();
		queue.add(AVLNode);
		
		while (!queue.isEmpty()) {
			AVLNode pollNode = queue.poll();
			System.out.println(String.format("value=%s, length=%s, balanceFactor=%s", pollNode.getValue(), pollNode.getLength(), pollNode.getBalanceFactor()));
			AVLNode leftNode = pollNode.getLeftNode();
			if (leftNode != null) {
				queue.add(leftNode);
			}
			AVLNode rightNode = pollNode.getRightNode();
			if (rightNode != null) {
				queue.add(rightNode);
			}
		}
	}
}

平衡二叉树增加实现，其中复用了二叉排序树功能，新增的单独标注

public class AVLTree {

	/**  ================================================*/
	/**  二叉树排序功能                                                    开始               */
	/**  ================================================*/
	public static AVLNode insert(AVLNode AVLNode, int value) {
		if (AVLNode == null) {
			AVLNode = new AVLNode(value);
		} else {
			int currentValue = AVLNode.getValue();
			if (currentValue > value) {
				AVLNode leftAVLNode = AVLNode.getLeftNode();
				leftAVLNode = insert(leftAVLNode, value);
				AVLNode.setLeftNode(leftAVLNode);
				leftAVLNode.setParentNode(AVLNode);
			} else if (currentValue < value) {
				AVLNode rightAVLNode = AVLNode.getRightNode();
				rightAVLNode = insert(rightAVLNode, value);
				AVLNode.setRightNode(rightAVLNode);
				rightAVLNode.setParentNode(AVLNode);
			} 
			// don't deal with currentValue equals with value
		}
		return AVLNode;
	}
	
	public static AVLNode delete(AVLNode root, int value) {
		AVLNode isExistAVLNode = search(root, value);
		if (isExistAVLNode == null) {
			return root;
		}
		
		// 标记待删除节点的父结点，其中若删除的是根节点，则parentAVLNode为空
		AVLNode parentAVLNode = null;
		AVLNode currentAVLNode = root;
		while (currentAVLNode != null && currentAVLNode.getValue() != value) {
			parentAVLNode = currentAVLNode;
			if (currentAVLNode.getValue() > value) {
				currentAVLNode = currentAVLNode.getLeftNode();
			} else {
				currentAVLNode = currentAVLNode.getRightNode();
			}
		}
		
		// 删除，分三种情况处理
		// 1. 叶子节点
		if (currentAVLNode.getLeftNode() == null && currentAVLNode.getRightNode() == null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(null);
				} else {
					parentAVLNode.setRightNode(null);
				}
			} else {
				root = null;
			}
		}
		
		// 2. 只存在一个子节点
		else if (currentAVLNode.getLeftNode() == null && currentAVLNode.getRightNode() != null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentAVLNode.getRightNode());
				} else {
					parentAVLNode.setRightNode(currentAVLNode.getRightNode());
				}
			} else {
				root = currentAVLNode.getRightNode();
			}
		} 
		else if (currentAVLNode.getLeftNode() != null && currentAVLNode.getRightNode() == null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentAVLNode.getLeftNode());
				} else {
					parentAVLNode.setRightNode(currentAVLNode.getLeftNode());
				}
			} else {
				root = currentAVLNode.getLeftNode();
			}
		}
		// 3. 存在两个子节点（采用替代法-可重用代码：找出被删除节点的右子树，找出最大的结点，替换被删除的结点）
		else if (currentAVLNode.getLeftNode() != null && currentAVLNode.getRightNode() != null) {
			// 3.1  找出右子树最大节点
			AVLNode currentMinAVLNode = currentAVLNode;
			while (currentMinAVLNode.getLeftNode() != null) {
				currentMinAVLNode = currentMinAVLNode.getLeftNode();
			}
			// 3.2 删除右子树最大节点
			root = delete(root, currentMinAVLNode.getValue());
			// 3.3 替换待删除节点
			currentMinAVLNode.setLeftNode(currentAVLNode.getLeftNode());
			currentMinAVLNode.setRightNode(currentAVLNode.getRightNode());
			// 3.4 设置父结点子引用
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentMinAVLNode);
				} else {
					parentAVLNode.setRightNode(currentMinAVLNode);
				}
			} else {
				root = currentMinAVLNode;
			}
		}
		
		return root;
	}
	
	public static AVLNode search(AVLNode AVLNode, int value) {
		if (AVLNode == null) {
			return null;
		}
		int currentValue = AVLNode.getValue();
		if (value == currentValue) {
			return AVLNode;
		} else if (currentValue > value) {
			AVLNode leftAVLNode = AVLNode.getLeftNode();
			return search(leftAVLNode, value);
		} else {
			AVLNode rightAVLNode = AVLNode.getRightNode();
			return search(rightAVLNode, value);
		}
	}
	
	public static AVLNode search2(AVLNode AVLNode, int value) {
		AVLNode currentAVLNode = AVLNode;
		while (currentAVLNode != null) {
			int currentValue = currentAVLNode.getValue();
			if (value == currentValue) {
				return currentAVLNode;
			} else if (currentValue > value) {
				currentAVLNode = currentAVLNode.getLeftNode();
			} else {
				currentAVLNode = currentAVLNode.getRightNode();
			}
		}
		return null;
	}
	
	
	public static AVLNode createBST(int[] nums) {
		AVLNode root = null;
		for (int value : nums) {
			root = insert(root, value);
		}
		return root;
	}
	
	/**  ================================================*/
	/**  二叉树排序功能                                                    结束               */
	/**  ================================================*/
	
	// ==================================================//
	
	/**  ================================================*/
	/**  平衡二叉树功能                                                    开始               */
	/**  ================================================*/
	
	public static AVLNode createAVL(int[] nums) {
		AVLNode root = null;
		for (int value : nums) {
			root = insertAVL(root, value);
		}
		return root;
	}
	
	public static AVLNode insertAVL(AVLNode AVLNode, int value) {
		// 复用原二叉排序树功能
		AVLNode root = insert(AVLNode, value);
		// 计算平衡影子
		resetBalanceFactor(root);
		// 平衡
		root = rebalance(root);

		return root;
	}

	/**
	 * <p>Description: 核心平衡方法</p>
	 */
	private static AVLNode rebalance(AVLNode root) {
		// 判断树是否满足平衡二叉树，不是平衡二叉树返回非平衡结点
		AVLNode nonAVLNode = getNonAVLNode(root);

		while (nonAVLNode != null) {
			// 找出调整结点
			AVLRotate aVLRotate = new RoutingAVLRotate();
			AVLNode rootAVLSubTree = aVLRotate.rotate(nonAVLNode);
			// 判断旋转结点是否为原根节点
			if (rootAVLSubTree.getParentNode() == null) {
				root = rootAVLSubTree;
			}
			resetBalanceFactor(root);
			// redo
			nonAVLNode = getNonAVLNode(root);
		}
		return root;
	}
	
	private static void resetBalanceFactor(AVLNode AVLNode) {
		AVLNode leftNode = AVLNode.getLeftNode();
		AVLNode rightNode = AVLNode.getRightNode();
		
		int leftAVLNodeLength = 0;
		if (leftNode != null) {
			resetBalanceFactor(leftNode);
			leftAVLNodeLength = leftNode.getLength();
		}
		int rightAVLNodeLength = 0;
		if (rightNode != null) {
			resetBalanceFactor(rightNode);
			rightAVLNodeLength = rightNode.getLength();
		}
		
		// 根据左右子树的的高度计算节点的高度、平衡因子
		int AVLNodeLength = Math.max(leftAVLNodeLength, rightAVLNodeLength) + 1;
		int AVLNodeBalanceFactor = leftAVLNodeLength - rightAVLNodeLength;
		AVLNode.setLength(AVLNodeLength);
		AVLNode.setBalanceFactor(AVLNodeBalanceFactor);
	}
	
	/**  
	 * <p>Description: 遍历搜索所有结点是否满足平衡二叉树-[通用]</p>  
	 */
	private static AVLNode getNonAVLNode(AVLNode node) {
		AVLNode nonAVLNode = null;
		
		// 使用层次遍历，找出平衡因子为+-2的结点
		Queue<AVLNode> queue = new LinkedBlockingDeque<>();
		queue.add(node);
		
		while (!queue.isEmpty()) {
			AVLNode pollNode = queue.poll();
			int balanceFactor = pollNode.getBalanceFactor();
			if (balanceFactor > 1 || balanceFactor < -1) {
				nonAVLNode = pollNode;
				break;
			}
			AVLNode leftNode = pollNode.getLeftNode();
			if (leftNode != null) {
				queue.add(leftNode);
			}
			AVLNode rightNode = pollNode.getRightNode();
			if (rightNode != null) {
				queue.add(rightNode);
			}
		}
		
		return nonAVLNode;
	}
	
	/**  ================================================*/
	/**  平衡二叉树功能                                                    结束               */
	/**  ================================================*/
	
}

核心平衡代码，这里抽象为单独的几个类实现

AVLRotate aVLRotate = new RoutingAVLRotate();
AVLNode rootAVLSubTree = aVLRotate.rotate(nonAVLNode);

平衡接口定义

public interface AVLRotate {
	AVLNode rotate(AVLNode rotateNode);
}

平衡路由选择

public class RoutingAVLRotate implements AVLRotate {
	@Override
	public AVLNode rotate(AVLNode rotateNode) {
		AVLRotate aVLRotate = null;
		if (rotateNode.getBalanceFactor() > 0) {
			AVLNode leftNode = rotateNode.getLeftNode();
			if (leftNode.getBalanceFactor() > 0) {
				// LL
				aVLRotate = new LLAVLRotate();
			} else {
				// LR
				aVLRotate = new LRAVLRotate();
			}
		} else {
			AVLNode rightNode = rotateNode.getRightNode();
			if (rightNode.getBalanceFactor() > 0) {
				// RL
				aVLRotate = new RLAVLRotate();
			} else {
				// RR
				aVLRotate = new RRAVLRotate();
			}
		}
		
		AVLNode rootAVLSubTree = aVLRotate.rotate(rotateNode);
		return rootAVLSubTree;
	}
}

LL实现

public class LLAVLRotate implements AVLRotate {
	@Override
	public AVLNode rotate(AVLNode rotateNode) {
		AVLNode rootAVLSubTree = rotateNode.getLeftNode(); 
		int value = rotateNode.getValue();
		AVLNode parentNode = rotateNode.getParentNode();
		rootAVLSubTree.setParentNode(parentNode);
		if (parentNode != null) {
			if (parentNode.getValue() > value) {
				parentNode.setLeftNode(rootAVLSubTree);
			} else {
				parentNode.setRightNode(rootAVLSubTree);
			}
		}
		
		// 调整
		rotateNode.setLeftNode(rootAVLSubTree.getRightNode());
		rootAVLSubTree.setRightNode(rotateNode);
		
		rotateNode.setParentNode(rootAVLSubTree);
		
		return rootAVLSubTree;
	}
}

LR实现

public class LRAVLRotate implements AVLRotate {
	@Override
	public AVLNode rotate(AVLNode rotateNode) {
		AVLNode leftNode = rotateNode.getLeftNode();
		AVLNode rootAVLSubTree = leftNode.getRightNode(); 
		int value = rotateNode.getValue();
		AVLNode parentNode = rotateNode.getParentNode();
		rootAVLSubTree.setParentNode(parentNode);
		if (parentNode != null) {
			if (parentNode.getValue() > value) {
				parentNode.setLeftNode(rootAVLSubTree);
			} else {
				parentNode.setRightNode(rootAVLSubTree);
			}
		}
		
		// 调整
		leftNode.setRightNode(rootAVLSubTree.getLeftNode());
		rotateNode.setLeftNode(rootAVLSubTree.getRightNode());
		rootAVLSubTree.setLeftNode(leftNode);
		rootAVLSubTree.setRightNode(rotateNode);
		
		rotateNode.setParentNode(rootAVLSubTree);
		leftNode.setParentNode(rootAVLSubTree);
		
		return rootAVLSubTree;
	}
}

RL实现

public class RLAVLRotate implements AVLRotate {
	@Override
	public AVLNode rotate(AVLNode rotateNode) {
		AVLNode rightNode = rotateNode.getRightNode();
		AVLNode rootAVLSubTree = rightNode.getLeftNode(); 
		int value = rotateNode.getValue();
		AVLNode parentNode = rotateNode.getParentNode();
		rootAVLSubTree.setParentNode(parentNode);
		if (parentNode != null) {
			if (parentNode.getValue() > value) {
				parentNode.setLeftNode(rootAVLSubTree);
			} else {
				parentNode.setRightNode(rootAVLSubTree);
			}
		}
		
		// 调整
		rightNode.setLeftNode(rootAVLSubTree.getRightNode());
		rotateNode.setRightNode(rootAVLSubTree.getLeftNode());
		rootAVLSubTree.setLeftNode(rotateNode);
		rootAVLSubTree.setRightNode(rightNode);
		
		rotateNode.setParentNode(rootAVLSubTree);
		rightNode.setParentNode(rootAVLSubTree);
		
		return rootAVLSubTree;
	}
}

RR实现

public class RRAVLRotate implements AVLRotate {
	@Override
	public AVLNode rotate(AVLNode rotateNode) {
		AVLNode rootAVLSubTree = rotateNode.getRightNode();
		int value = rotateNode.getValue();
		AVLNode parentNode = rotateNode.getParentNode();
		rootAVLSubTree.setParentNode(parentNode);
		if (parentNode != null) {
			if (parentNode.getValue() > value) {
				parentNode.setLeftNode(rootAVLSubTree);
			} else {
				parentNode.setRightNode(rootAVLSubTree);
			}
		}
		
		// 调整
		rotateNode.setRightNode(rootAVLSubTree.getLeftNode());
		rootAVLSubTree.setLeftNode(rotateNode);
		
		rotateNode.setParentNode(rootAVLSubTree);
		
		return rootAVLSubTree;
	}
}

测试类

public class AVLTreeTest6 {
	public static void main(String[] args) {
		int nums[] = { 4, 1, 2, 5, 0, 7, 9, 8, 3, 6 };
		AVLNode tree = AVLTree.createAVL(nums);
		AVLLevelTraversal.traversal(tree);
	}
}

输出结果

----------------------
value=5, length=4, balanceFactor=0
value=2, length=3, balanceFactor=0
value=8, length=3, balanceFactor=1
value=1, length=2, balanceFactor=1
value=4, length=2, balanceFactor=1
value=7, length=2, balanceFactor=1
value=9, length=1, balanceFactor=0
value=0, length=1, balanceFactor=0
value=3, length=1, balanceFactor=0
value=6, length=1, balanceFactor=0

推理过程{ 4, 1, 2, 5, 0, 7, 9, 8, 3, 6 }

  • { 1, 2, 5, 0, 7, 9, 8, 3, 6 } -> 4
4
  • { 2, 5, 0, 7, 9, 8, 3, 6 } -> 1
  4
 /
1
  • { 5, 0, 7, 9, 8, 3, 6 } -> 2
  4
 /
1
 \
  2

LR旋转(412)

  2
 / \
1   4
  • { 0, 7, 9, 8, 3, 6 } -> 5
  2
 / \
1   4
     \
      5
  • { 7, 9, 8, 3, 6 } -> 0
    2
   / \
  1   4
 /     \
0       5
  • { 9, 8, 3, 6 } -> 7
    2
   / \
  1   4
 /     \
0       5
         \
          7

RR旋转(457)

    2
   / \
  1   5
 /   / \
0   4   7
  • { 8, 3, 6 } -> 9
    2
   / \
  1   5
 /   / \
0   4   7
         \
          9
  • { 3, 6 } -> 8
    2
   / \
  1   5
 /   / \
0   4   7
         \
          9
         /
        8

RR旋转(257)

      5
     / \
    2   7
   / \   \
  1   4   9
 /       /
0       8

RL旋转(798)

        5
      /   \
    2       8
   / \     / \
  1   4   7   9
 /      
0
  • { 6 } -> 3
        5
      /   \
    2       8
   / \     / \
  1   4   7   9
 /   /   
0   3
  • { } -> 6
        5
      /   \
    2       8
   / \     / \
  1   4   7   9
 /   /   /
0   3   6

层序遍历结果对比-一致

----------------------
value=5, length=4, balanceFactor=0
value=2, length=3, balanceFactor=0
value=8, length=3, balanceFactor=1
value=1, length=2, balanceFactor=1
value=4, length=2, balanceFactor=1
value=7, length=2, balanceFactor=1
value=9, length=1, balanceFactor=0
value=0, length=1, balanceFactor=0
value=3, length=1, balanceFactor=0
value=6, length=1, balanceFactor=0

核心代码说明，并轻松实现平衡二叉树删除功能

插入方法

	public static AVLNode insertAVL(AVLNode AVLNode, int value) {
		// 复用原二叉排序树功能
		AVLNode root = insert(AVLNode, value);
		// 计算平衡影子
		resetBalanceFactor(root);
		// 平衡
		root = rebalance(root);

		return root;
	}

我们可以注意到，核心方法是root = rebalance(root);方法，实现了平衡，那么我们如果实现删除后平衡如何实现，非常简单，即

	public static AVLNode deleteAVL(AVLNode AVLNode, int value) {
		// 复用原二叉排序树功能
		AVLNode root = delete(AVLNode, value);
		// 计算平衡影子
		resetBalanceFactor(root);
		// 平衡
		root = rebalance(root);
		
		return root;
	}

测试在原有基础上删除9

        5
      /   \
    2       8
   / \     / \
  1   4   7   9
 /   /   /
0   3   6

二叉排序树删除变化后

        5
      /   \
    2       8
   / \     /
  1   4   7  
 /   /   /
0   3   6

平衡旋转（LL旋转）

        5
      /   \
    2       7
   / \     / \
  1   4   6   8
 /   /  
0   3

测试类

public class AVLTreeTest {
	public static void main(String[] args) {
		int nums[] = { 4, 1, 2, 5, 0, 7, 9, 8, 3, 6 };
		AVLNode tree = AVLTree.createAVL(nums);
		AVLLevelTraversal.traversal(tree);
		
		AVLNode deleteTree = AVLTree.delete(tree, 9);
		AVLLevelTraversal.traversal(deleteTree);
	}
}

输出，预期一致

----------------------
value=5, length=4, balanceFactor=1
value=2, length=3, balanceFactor=0
value=7, length=2, balanceFactor=0
value=1, length=2, balanceFactor=1
value=4, length=2, balanceFactor=1
value=6, length=1, balanceFactor=0
value=8, length=1, balanceFactor=0
value=0, length=1, balanceFactor=0
value=3, length=1, balanceFactor=0

当然，这个原二叉排序树删除逻辑有点问题，删除节点后，还需要设置AVLNode节点的parentNode引用，这是因为我们是从二叉排序树过渡来的，修改删除代码public static AVLNode delete(AVLNode root, int value)；

添加三次设置父对象引入即可，分别是

  1. currentAVLNode.getRightNode().setParentNode(parentAVLNode);
  2. currentAVLNode.getLeftNode().setParentNode(parentAVLNode);
  3. currentMinAVLNode.setParentNode(parentAVLNode);
	public static AVLNode delete(AVLNode root, int value) {
		AVLNode isExistAVLNode = search(root, value);
		if (isExistAVLNode == null) {
			return root;
		}
		
		// 标记待删除节点的父结点，其中若删除的是根节点，则parentAVLNode为空
		AVLNode parentAVLNode = null;
		AVLNode currentAVLNode = root;
		while (currentAVLNode != null && currentAVLNode.getValue() != value) {
			parentAVLNode = currentAVLNode;
			if (currentAVLNode.getValue() > value) {
				currentAVLNode = currentAVLNode.getLeftNode();
			} else {
				currentAVLNode = currentAVLNode.getRightNode();
			}
		}
		
		// 删除，分三种情况处理
		// 1. 叶子节点
		if (currentAVLNode.getLeftNode() == null && currentAVLNode.getRightNode() == null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(null);
				} else {
					parentAVLNode.setRightNode(null);
				}
			} else {
				root = null;
			}
		}
		
		// 2. 只存在一个子节点
		else if (currentAVLNode.getLeftNode() == null && currentAVLNode.getRightNode() != null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentAVLNode.getRightNode());
				} else {
					parentAVLNode.setRightNode(currentAVLNode.getRightNode());
				}
			} else {
				root = currentAVLNode.getRightNode();
			}
			currentAVLNode.getRightNode().setParentNode(parentAVLNode);
		} 
		else if (currentAVLNode.getLeftNode() != null && currentAVLNode.getRightNode() == null) {
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentAVLNode.getLeftNode());
				} else {
					parentAVLNode.setRightNode(currentAVLNode.getLeftNode());
				}
			} else {
				root = currentAVLNode.getLeftNode();
			}
			currentAVLNode.getLeftNode().setParentNode(parentAVLNode);
		}
		// 3. 存在两个子节点（采用替代法-可重用代码：找出被删除节点的右子树，找出最大的结点，替换被删除的结点）
		else if (currentAVLNode.getLeftNode() != null && currentAVLNode.getRightNode() != null) {
			// 3.1  找出右子树最大节点
			AVLNode currentMinAVLNode = currentAVLNode.getRightNode();
			while (currentMinAVLNode.getLeftNode() != null) {
				currentMinAVLNode = currentMinAVLNode.getLeftNode();
			}
			// 3.2 删除右子树最大节点
			root = delete(root, currentMinAVLNode.getValue());
			// 3.3 替换待删除节点
			currentMinAVLNode.setLeftNode(currentAVLNode.getLeftNode());
			currentMinAVLNode.setRightNode(currentAVLNode.getRightNode());
			// 3.4 设置父结点子引用
			if (parentAVLNode != null) {
				if (parentAVLNode.getValue() > value) {
					parentAVLNode.setLeftNode(currentMinAVLNode);
				} else {
					parentAVLNode.setRightNode(currentMinAVLNode);
				}
			} else {
				root = currentMinAVLNode;
			}
			currentMinAVLNode.setParentNode(parentAVLNode);
		}
		
		return root;
	}

请自行验证

到这里就完成了平衡功能，接下来我们将学习红黑树

本文地址：https://blog.csdn.net/dengjili/article/details/112851332

相关标签： 算法

上一篇： 将Bean放入Spring容器中的五种方式

下一篇： 利用laravel搭建一个迷你博客实战教程

推荐阅读