2023面试高手

这个屌丝很懒，什么也没留下！

热门标签

平衡二叉树（AVL树）算法 Java实现_计算二叉树bf值java

作者：2023面试高手 | 2024-05-27 13:25:21

踩

计算二叉树bf值java

定义：

平衡二叉树（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为根的二叉排序树做右旋处理 <p>
	 * 处理之后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 为根的二叉排序树做左旋处理<p>
	 * 处理之后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结点为根的二叉树作左平衡旋转处理<p>
	 * 以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<TreeNode> queue = new ConcurrentLinkedQueue<>();
		ConcurrentLinkedQueue<TreeNode> 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<TreeNode> source, ConcurrentLinkedQueue<TreeNode> 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 + "]";
	}
	
	
	
	
}

运行结果

代码所示平衡二叉树的构建过程

右平衡各种情况图（类似左平衡）

参考文章：http://www.cnblogs.com/javaminer/p/3462468.html

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/632219