平衡二叉树java实现（插入、删除、平衡调整）_java 二叉平衡树

目录

一、排序二叉树与平衡二叉树区别

二、失衡类型及失衡调整

1、RR型

2、LL型

3、RL型

4、LR型

三、插入节点

1、插入操作

2、失衡节点

3、失衡类型

四、删除节点

1、删除操作

2、失衡节点

3、失衡类型 

五、代码实现

1、平衡二叉树java类

2、测试类

3、测试打印

六、相关证明

1、插入操作，只需调整最小失衡子树，调整后整颗树会恢复平衡

2、删除节点无子节点，失衡节点只有一个

---

一、排序二叉树与平衡二叉树区别

排序二叉树：是一颗二叉树，且所有节点的右孩子比自身大，自身比左孩子大

平衡二叉树：在排序二叉树的定义之下，再加一个条件，即所有节点左子树和右子树高度之差的绝对值不大于1

二、失衡类型及失衡调整

1、RR型

1）失衡节点作为旋转节点

2）失衡节点的子节点作为中心节点

3）旋转节点绕中心节点左旋，如果中心节点存在左子树，那么该左子树变成旋转节点的右子树

4）再把中心节点挂到原来的父节点上

5）总结：左旋

2、LL型

同RR型相反，右旋，略过

3、RL型

1）先以失衡节点的子节点作为旋转节点，失衡节点的孙子节点作为中心节点，右旋

2）如果中心节点存在右子树，则该右子树变成旋转节点的左子树

3）将中心节点连接到失衡节点的右孩子处

4）再已失衡节点作为旋转节点，以失衡节点的孙子节点作为中心节点，左旋

5）如果中心节点存在左子树，则该左子树变成旋转节点的右子树

6）将中心节点挂到原来的父节点上

7）总结：先右旋，后左旋

4、LR型

同RL型相反，先左旋，后右旋，略过

三、插入节点

1、插入操作

从根节点向下遍历，找到插入节点的父节点，然后插入

2、失衡节点

1）插入新节点可能会导致多个节点失衡

2）插入造成的失衡，失衡节点只可能是插入节点的父节点或更上层的祖先节点（爷爷、祖父...）

3）插入操作，只需调整最小失衡子树，调整后整颗树会恢复平衡，证明见6.1

3、失衡类型

1）从插入节点向上遍历，直到找到第一个失衡节点（最小失衡子树根节点）

2）从失衡节点向插入节点遍历，前两个路径即失衡类型

3）举例

四、删除节点

1、删除操作

1）待删除节点无子节点——直接删除（节点替换，用null替换删除节点）

2）待删除节点仅有左子树或右子树——直接用左子树或右子树替换删除的节点（节点替换，用直接子节点替换删除节点）

3）待删除节点既有左子树，又有右子树——找右子树中最小的节点minNode，用minNode的值替换删除节点的值（值替换），再用minNode的右子树替换minNode（节点替换）

• 找到待删除节点右子树中最小的节点minNode，即26节点
• 用26节点的值替换待删除节点的值（值替换）
• 删除掉minNode（节点替换）
• 注：minNode也可以找被删除节点左子树最大节点

2、失衡节点

1）删除节点无子节点

• 失衡节点只可能是被删除被删除节点的上层节点（父亲、爷爷、祖父...），子树1、子树2仍然保持平衡

• 失衡节点只可能有一个，证明见6.2

2）删除节点有且仅有左子树（右子树）

• 失衡节点只可能是被删除被删除节点的上层节点（父亲、爷爷、祖父...），子树1、子树2、子树3仍然保持平衡

• 失衡节点只可能有一个，证明同6.2

3）删除节点既有左子树又有右子树

• 失衡节点只可能是minNode（被删除节点右子树最小节点的父节点）的祖先结点（父亲、爷爷、祖父...）

• 失衡节点只可能有一个，证明同6.2

3、失衡类型 

从失衡节点向左右子树中，较高的子树遍历，得到前两个路径即为失衡类型，举例

五、代码实现

话不多说，show you my code

1、平衡二叉树java类

package com.yqc.tree;
 
import lombok.Data;
import java.util.Objects;
 
/**
 * @author Rickon
 * @date 2023/11/16 18:21
 * @description
 * 1、一个根节点属性root
 * 2、主要方法：
 * 插入、删除、调整、左旋、右旋、节点替换、查找指定值节点、判断节点是否失衡、判断右子树是否高于左子树
 * 前序遍历、中序遍历、后续遍历、层序遍历
 * 树的高度、叶子节点数、所有节点数、第i层节点数
 */
 
@Data
public class BSTree {
 
	// 操作类型
	private static final int OPERATION_INSERT = 1;
	private static final int OPERATION_DELETE = 2;
 
	// 根节点属性
	private Node root;
 
	/**
	 * 插入
	 */
	public void insert(Integer val) {
		Node newNode = new Node(val, null);
 
		// 插入第一个节点
		if (null == this.root) {
			this.root = newNode;
			return;
		}
 
		// 找到待插入节点的父节点
		Node temp = root;
		Node parent = null;
		while (null != temp) {
			parent = temp;
			if (val > temp.val)
				temp = temp.rChild;
			else if (val < temp.val)
				temp = temp.lChild;
			else
				// 待插入节点已存在
				return;
		}
 
		// 插入
		newNode.parent = parent;
		if (val > parent.val)
			parent.rChild = newNode;
		else
			parent.lChild = newNode;
 
		// 调整至平衡
		adjust(newNode, OPERATION_INSERT);
	}
 
	/**
	 * 删除
	 */
	public void remove(Integer val) {
		// 找到待删除节点
		Node removedNode = get(val);
		if (null == removedNode)
			return;
 
		// 保存节点，用来寻找失衡节点的起始节点
		Node beginNode = null;
 
		// 分情况处理
		if (null == removedNode.lChild && null == removedNode.rChild) {
			// 失衡节点只能是删除节点上层节点（父亲，爷爷，祖父...）
			beginNode = removedNode.parent;
			// 直接删除
			replace(removedNode, null);
		} else if (null != removedNode.lChild && null != removedNode.rChild) {
			// 找右子树中最小的节点minNode（也可找左子树中最大的节点）
			Node minNode = null;
			Node temp = removedNode.rChild;
			while (null != temp) {
				minNode = temp;
				temp = temp.lChild;
			}
			// 失衡节点只能是minNode上层节点（父亲，爷爷，祖父...）
			beginNode = minNode.parent;
			// minNode的右子树替换minNode（右子树提升，相对位置变化，右子树最多只有一个节点，否则minNode就失衡了）
			replace(minNode, minNode.rChild);
			// 待删除节点val替换成minNode的val（节点值互换，相对位置不变）
			removedNode.val = minNode.val;
		} else {
			// 失衡节点只能是删除节点上层节点（父亲，爷爷，祖父...）
			beginNode = removedNode.parent;
			// 保存待删除节点左子树或右子树
			Node child;
			if (null != removedNode.lChild)
				child = removedNode.lChild;
			else
				child = removedNode.rChild;
			// 左子树或右子树替换待删除节点
			replace(removedNode, child);
		}
 
		// 调整
		adjust(beginNode, OPERATION_DELETE);
	}
 
	/**
	 * 用target替换source的位置（位置替换，注意区别值替换）
	 */
	private void replace(Node source, Node target) {
		if (source == null)
			throw new RuntimeException("被替换节点不能为空");
		Node parent = source.parent;
 
		// 用null替换
		if (target == null) {
			if (source.val > parent.val)
				parent.rChild = null;
			else
				parent.lChild = null;
			source.parent = null;
			source.lChild = null;
			source.rChild = null;
			return;
		}
 
		if (Objects.equals(source.val, target.val))
			throw new RuntimeException("被替换节点与目标几点值相同");
 
		// 用非空节点替换
		if (source.val > parent.val)
			parent.rChild = target;
		else
			parent.lChild = target;
		target.parent = parent;
		source.parent = null;
		source.lChild = null;
		source.rChild = null;
	}
 
	/**
	 * 查询指定节点
	 */
	private Node get(Integer val) {
		Node temp = root;
		Node removedNode = null;
		while (null != temp) {
			if (val > temp.val)
				temp = temp.rChild;
			else if (val < temp.val)
				temp = temp.lChild;
			else {
				removedNode = temp;
				break;
			}
		}
 
		return removedNode;
	}
 
	/**
	 * 插入或删除节点后，重新调整为平衡二叉树
	 * @param node 插入操作——插入节点，删除操作——找失衡节点的起始节点
	 * @param operationType 操作类型
	 */
	private void adjust(Node node, int operationType) {
		// 从插入或起始节点向上遍历，找失衡节点（最小失衡子树根节点）
		Node temp = node;
		Node unbalancedNode = null;
		while (temp != null) {
			if (isUnbalanced(temp)) {
				unbalancedNode = temp;
				break;
			} else {
				temp = temp.parent;
			}
		}
		if (null == unbalancedNode)
			return;
 
		// 判断失衡类型
		StringBuilder sb = new StringBuilder();
		temp = unbalancedNode;
		Node unbalancedChildNode = null;
		Node unbalancedGrandChildNode = null;
		if (OPERATION_INSERT == operationType) {
			// 从失衡节点向插入节点搜索两次，判断失衡类型
			for (int i=0; i<2; ++i) {
				if (node.val > temp.val) {
					sb.append("R");
					temp = temp.rChild;
				} else {
					sb.append("L");
					temp = temp.lChild;
				}
				// 记录【失衡节点儿子节点】和【失衡节点孙子节点】
				if (unbalancedChildNode == null)
					unbalancedChildNode = temp;
				else
					unbalancedGrandChildNode = temp;
			}
		} else {
			// 从失衡节点向更高子树遍历搜索两次，判断失衡类型
			for (int i=0; i<2; ++i) {
				if (isRChildHigher(temp)) {
					sb.append("R");
					temp = temp.rChild;
				} else {
					sb.append("L");
					temp = temp.lChild;
				}
				// 记录【失衡节点儿子节点】和【失衡节点孙子节点】
				if (unbalancedChildNode == null)
					unbalancedChildNode = temp;
				else
					unbalancedGrandChildNode = temp;
			}
		}
		String unbalancedType = sb.toString();
 
		// 根据失衡类型调整
		// 记录失衡节点的父节点，最小失衡子树调整后需要挂在该父节点上，如果为空，说明根节点就是最小失衡子树的根节点
		Node parent = unbalancedNode.parent;
		boolean isRChild = false;
		if (null != parent) {
			isRChild = unbalancedNode.val > parent.val;
		}
		switch (unbalancedType) {
			case "RR":
				// 左旋
				lRotate(unbalancedNode, unbalancedChildNode, parent, isRChild);
				break;
			case "RL":
				// 先右旋，后左旋
				rRotate(unbalancedChildNode, unbalancedGrandChildNode, unbalancedNode, true);
				lRotate(unbalancedNode, unbalancedGrandChildNode, parent, isRChild);
				break;
			case "LL":
				// 右旋
				rRotate(unbalancedNode, unbalancedChildNode, parent, isRChild);
				break;
			case "LR":
				// 先左旋，后右旋
				lRotate(unbalancedChildNode, unbalancedGrandChildNode, unbalancedNode, false);
				rRotate(unbalancedNode, unbalancedGrandChildNode, parent, isRChild);
				break;
			default:
				throw new RuntimeException("失衡类型异常");
		}
	}
 
	/**
	 * 判断节点右子树高度是否高于左子树
	 */
	private boolean isRChildHigher(Node root) {
		if (root == null) {
			return false;
		}
 
		return height(root.getRChild()) > height(root.getLChild());
	}
 
	/**
	 * 左旋
	 * @param rotatedNode 旋转节点
	 * @param centerNode 中心节点
	 * @param parent 旋转后，中心节点的父节点
	 * @param isRChild 旋转后，中心节点是否作为parent的右孩子
	 */
	private void lRotate(Node rotatedNode, Node centerNode, Node parent, boolean isRChild) {
		// 保存【中心节点】的左孩子
		Node centerNodeLChild = centerNode.lChild;
		// 【旋转节点】变成【中心节点】的左孩子
		centerNode.lChild = rotatedNode;
		rotatedNode.parent = centerNode;
		rotatedNode.rChild = null;
		// 【中心节点】的左孩子变成【旋转节点】的右孩子
		if (centerNodeLChild != null) {
			rotatedNode.rChild = centerNodeLChild;
			centerNodeLChild.parent = rotatedNode;
		}
		// 旋转后重新连接到parent，parent为null，表示调整了整棵树
		if (null == parent)
			root = centerNode;
		else if (isRChild)
			parent.rChild = centerNode;
		else
			parent.lChild = centerNode;
		centerNode.parent = parent;
	}
 
	/**
	 * 右旋
	 * @param rotatedNode 旋转节点
	 * @param centerNode 中心节点
	 * @param parent 旋转后，中心节点的父节点
	 * @param isRChild 旋转后，中心节点是否作为parent的右孩子
	 */
	private void rRotate(Node rotatedNode, Node centerNode, Node parent, boolean isRChild) {
		// 保存【中心节点】的左孩子
		Node centerNodeRChild = centerNode.rChild;
		// 【旋转节点】变成【中心节点】的右孩子
		centerNode.rChild = rotatedNode;
		rotatedNode.parent = centerNode;
		rotatedNode.lChild = null;
		// 【中心节点】的左孩子变成【旋转节点】的右孩子
		if (centerNodeRChild != null) {
			rotatedNode.lChild = centerNodeRChild;
			centerNodeRChild.parent = rotatedNode;
		}
		// 旋转后重新连接到parent，parent为null，表示调整了整棵树
		if (null == parent)
			root = centerNode;
		else if (isRChild)
			parent.rChild = centerNode;
		else
			parent.lChild = centerNode;
		centerNode.parent = parent;
	}
 
	/**
	 * 判断节点是否是失衡
	 */
	private boolean isUnbalanced(Node root) {
		if (null == root) {
			return false;
		}
 
		return Math.abs(height(root.lChild) - height(root.rChild)) > 1;
	}
 
	/**
	 * 前序遍历
	 */
	public void preOrder() {
		preOrder(this.root);
		System.out.println();
	}
	private void preOrder(Node root) {
		if (null == root) {
			return;
		}
		System.out.print(root + " ");
		preOrder(root.lChild);
		preOrder(root.rChild);
	}
 
	/**
	 * 中序遍历
	 */
	public void midOrder() {
		midOrder(this.root);
		System.out.println();
	}
	private void midOrder(Node root) {
		if (null == root) {
			return;
		}
		midOrder(root.lChild);
		System.out.print(root + " ");
		midOrder(root.rChild);
	}
 
	/**
	 * 后序遍历
	 */
	public void postOrder() {
		postOrder(this.root);
		System.out.println();
	}
	private void postOrder(Node root) {
		if (null == root) {
			return;
		}
		postOrder(root.lChild);
		postOrder(root.rChild);
		System.out.print(root + " ");
	}
 
	/**
	 * 层序遍历
	 */
	public void levelOrder() {
		if (null == root) {
			return;
		}
 
		// 根节点入队
		Queue queue = new Queue(10);
		queue.push(root);
		// 队列不空
		while (!queue.isEmpty()) {
			// 出队并打印
			Node node = queue.pop();
			System.out.print(node + " ");
			// 左子树入队
			if (null != node.lChild) {
				queue.push(node.lChild);
			}
			// 右子树入队
			if (null != node.rChild) {
				queue.push(node.rChild);
			}
		}
		System.out.println();
	}
 
	/**
	 * 第i层的节点数
	 */
	public int countOfLevel(int i) {
		return countOfLevel(root, i);
	}
	private int countOfLevel(Node root, int i) {
		if (null == root) {
			return 0;
		}
 
		if (1 == i) {
			return 1;
		}
 
		return countOfLevel(root.lChild, i - 1) + countOfLevel(root.rChild, i - 1);
	}
 
	/**
	 * 树的高度
	 */
	public int height() {
		return height(root);
	}
	private int height(Node root) {
		if (null == root) {
			return 0;
		}
 
		return Math.max(1 + height(root.lChild), 1 + height(root.rChild));
	}
 
	/**
	 * 叶子节点个数
	 */
	public int leafCount() {
		return leafCount(root);
	}
	private static int leafCount(Node root) {
		if (null == root) {
			return 0;
		}
 
		if (null == root.lChild && null == root.rChild) {
			return 1;
		}
 
		return leafCount(root.lChild) + leafCount(root.rChild);
	}
 
	/**
	 * 所有节点个数
	 */
	public int size() {
		return size(root);
	}
	private static int size(Node root) {
		if (null == root) {
			return 0;
		}
 
		return 1 + size(root.lChild) + size(root.rChild);
	}
 
	@Data
	static class Node{
		Integer val;
		Node parent;
		Node lChild;
		Node rChild;
 
		public Node(Integer val, Node parent) {
			this.val = val;
			this.parent = parent;
		}
 
		// 一定要重写toString()，因为父子节点相互持有对方的引用，不重写会导致循环打印，stackOverFlow
		@Override
		public String toString() {
			return val + "";
		}
	}
 
	@Data
	static class Queue {
		Node[] queue;
		int size;
		int head;
		int tail;
		int capacity;
 
		public Queue(int capacity) {
			this.queue = new Node[capacity];
			this.size = 0;
			this.head = 0;
			this.tail = 0;
			this.capacity = capacity;
		}
 
		/**
		 * 判断队列是否已满
		 */
		public boolean isFull() {
			return this.getSize() >= this.getCapacity();
		}
 
		/**
		 * 判断队列是否为空
		 */
		public boolean isEmpty() {
			return this.getSize() <= 0;
		}
 
		/**
		 * 入队
		 */
		public boolean push(Node element) {
			if (isFull()) {
				throw new RuntimeException("队列已满");
			}
 
			queue[tail] = element;
			tail = (tail + 1) % capacity;
			size++;
			return true;
		}
 
		/**
		 * 出队
		 */
		public Node pop() {
			if (isEmpty()) {
				throw new RuntimeException("队列为空");
			}
 
			Node element = queue[head];
			head = (head + 1) % capacity;
			size--;
			return element;
		}
	}
}

2、测试类

package com.yqc.tree;
 
 
/**
 * @author Rickon
 * @date 2023/11/14 20:34
 * @description
 */
public class Test {
 
	public static void main(String[] args) {
		BSTree tree = new BSTree();
		tree.insert(10);
		tree.insert(20);
		tree.insert(5);
		tree.insert(37);
		tree.insert(39);
		tree.insert(15);
		Test.print(tree);
		tree.remove(10);
		tree.remove(39);
		tree.remove(37);
		Test.print(tree);
		System.out.println("节点总数：" + tree.size());
		System.out.println("叶子节点数：" + tree.leafCount());
		System.out.println("第2层节点数：" + tree.countOfLevel(2));
		System.out.println("树的高度：" + tree.height());
	}
 
	private static void print(BSTree tree) {
		System.out.print("先序：");tree.preOrder();
		System.out.print("中序：");tree.midOrder();
		System.out.print("后序：");tree.postOrder();
		System.out.print("层序：");tree.levelOrder();
	}
}

3、测试打印

六、相关证明

1、插入操作，只需调整最小失衡子树，调整后整颗树会恢复平衡

1）在节点插入前，节点20的左子树高度为H+1；插入后，节点20的左子树高度为H+2，导致节点20衡

2）在节点插入前，节点10的右子树高度为H；插入后，节点10的右子树高度由H增高为H+1，导致节点10失衡

3）节点插入后，10和20两个节点失衡，最小失衡子树为虚线绿框所示，根节点即失衡节点10

4）以10为根节点的子树，是20节点的左子树，在新节点插入前，其高度为H+1，插入后，高度为H+2（变为最小失衡子树），在调整平衡后（调整最小失衡子树），高度又变为H+1，所以节点20从平衡变为失衡，又因为最小失衡子树的调整，20节点重新达到平衡

2、删除节点无子节点，失衡节点只有一个

1）删除节点18，如果要使得节点10失衡，那么在删除操作前，节点10的左子树【子树1】的高度必须比右子树高1

2）删除节点18后，节点10的右子树高度减1，导致节点10失衡

3）但是从节点20看，它的左子树高度不变不会因为节点18的删除而改变，仍然保持平衡

4）同理，更高层祖先节点也不会失衡

3、删除既有左子树又有右子树的节点，失衡节点只可能是minNode的父节点