首页 > 其他分享 >平衡二叉树

平衡二叉树

时间:2022-08-22 08:45:42浏览次数:67  
标签:左子 结点 right 右子 二叉树 平衡 null left

1.为什么需要平衡二叉树?

二叉排序树可能的存在的问题

给你一个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST), 并分析问题所在.

1661085324274

上图BST存在的问题分析:

  1. 左子树全部为空,从形式上看,更像一个单链表。
  2. 插入速度没有影响
  3. 查询速度明显降低(因为需要依次比较), 不能发挥BST的优势,因为每次还需要比较左子树,其查询速度比单链表还慢

上面问题怎么解决呢?

解决方案-平衡二叉树(AVL)

2.平衡二叉树基本介绍

  1. 平衡二叉树也叫平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树, 可以保证查询效率较高
  2. 具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
  3. 举例说明, 看看下面哪些AVL树

1661085870828

3.AVL高度求解

3.1代码结构

1661088526263

3.2代码实现

// 返回左子树的高度
	public int leftHeight() {
		if (left == null) {
			return 0;
		}
		return left.height();
	}

	// 返回右子树的高度
	public int rightHeight() {
		if (right == null) {
			return 0;
		}
		return right.height();
	}

	// 返回以当前结点为根结点的高度,以该结点为根结点的树的高度
	public int height() {
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
	}

3.3测试代码

public static void main(String[] args) {
		int[] arr = {4,3,6,5,7,8};
		//创建一个AVLTree对象
		AVLTree avlTree = new AVLTree();
		//添加结点
		for(int i = 0; i<arr.length; i++){
			avlTree.add(new Node(arr[i]));
		}
		
		//中序遍历
		System.out.println("中序遍历之后");
		avlTree.infixOrder();
		
		System.out.println("没有平衡之前=====");
		System.out.println("树的高度=" + avlTree.getRoot().height());//4
		System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());//1
		System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());//3
		

	}

3.4测试结果

1661088716387

4.AVL实现左旋转

4.0图解

1661089294231

4.1代码结构

1661090728311

4.2代码实现

// 左旋转方法
	public void leftRotate() {
		//创建新的结点,以当前根结点的值
		Node newNode = new Node(value);
		//把新的结点的左子树设置成当前结点的左子树
		newNode.left = left;
		//把新结点的右子树设置成当前结点的右子结点的左子树
		newNode.right = right.left;
		//把当前结点的值替换成当前结点的右子结点的值
		value = right.value;
		//把当前结点的右子树设置成当前结点的右子树的右子树
		right = right.right;//相当于跳过一个结点
		//把当前结点的左子树(左子结点)设置成新的结点
		left = newNode;		
	}

需要在add()方法中调用旋转方法

// 编写增加结点的方法
	public void add(Node node) {
		if (node == null) {
			return;
		}
		// 判断当前结点与左右子树值的大小关系
		if (node.value < this.value) {
			// 左子树的值小,向左子树增加
			if (this.left == null) {
				// 左子树为空,直接添加
				this.left = node;
			} else {
				// 左子树不为空,向左子树增加
				this.left.add(node);
			}
		} else {
			// 传入的node结点的值大于当前结点,增加到右子树
			if (this.right == null) {
				this.right = node;
			} else {
				// 递归增加到右子树
				this.right.add(node);
			}
		}
		
		//当添加完一个结点之后,如果 (右子树的高度-左子树的高度)> 1,则左旋转
		if (rightHeight() - leftHeight() > 1) {
			
			leftRotate();//左旋转
		}

	}

4.3测试代码和结果

1661090874372

5.AVL实现右旋转

5.0图解

1661091877130

5.1代码结构

1661091952536

5.2代码实现

//右旋转方法
	public void rightRotate(){
		//1.创建一个新结点newNode,新结点的值等于当前结点的值
		Node newNode = new Node(value);
		//2.把新结点的右子树设置成当前结点的右子树
		newNode.right = right;
		//3.把新结点的左子树设置成当前结点的左子树的右子树
		newNode.left = left.right;
		//4.把当前结点的值换成当前结点的左子结点
		value = left.value;
		//5.把当前结点的左子树设置成左子树的左子树
		left = left.left;
		//6.把当前结点的右子树设置成新结点(难)
		right = newNode;
	}

需要在add()方法中调用旋转方法

// 当添加完一个结点之后,如果 (左子树的高度-右子树的高度)> 1,则右旋转
		if (leftHeight() - rightHeight()  > 1) {

			rightRotate();// 右旋转
		}

5.3测试代码和结果

旋转前

1661092146069

旋转后

1661092310109

6.AVL实现双旋转

6.0图解

1661092496805

上面右旋转之后问题没有得到解决

问题分析

1.当符合右旋转的条件时
2.如果它的左子树的右子树高度大于它的左子树的高度

3.先对当前这个结点的左节点进行左旋转
4.再对当前结点进行右旋转的操作即可

6.1代码结构

1661093723951

6.2代码实现

// 编写增加结点的方法
	public void add(Node node) {
		if (node == null) {
			return;
		}
		// 判断当前结点与左右子树值的大小关系
		if (node.value < this.value) {
			// 左子树的值小,向左子树增加
			if (this.left == null) {
				// 左子树为空,直接添加
				this.left = node;
			} else {
				// 左子树不为空,向左子树增加
				this.left.add(node);
			}
		} else {
			// 传入的node结点的值大于当前结点,增加到右子树
			if (this.right == null) {
				this.right = node;
			} else {
				// 递归增加到右子树
				this.right.add(node);
			}
		}
		
		//当添加完一个结点之后,如果 (右子树的高度-左子树的高度)> 1,则左旋转
		if (rightHeight() - leftHeight() > 1) {
			// 如果它的右子树的左子树的高度大于它的右子树的高度
			if (right != null && right.leftHeight() > right.rightHeight()) {
				// 先对当前结点的右节点(右子树)进行右旋转
				right.rightRotate();
				// 再对当前结点进行左旋转
				leftRotate();
			} else {
				// 直接左旋转
				leftRotate();
			}
			return;//必须要
		}
		
		// 当添加完一个结点之后,如果 (左子树的高度-右子树的高度)> 1,则右旋转
		if (leftHeight() - rightHeight()  > 1) {
			// 如果它的左子树的右子树的高度大于它的左子树的高度
			if (left != null && left.rightHeight() > left.leftHeight()) {
				//先对当前结点的左节点(左子树)进行左旋转
				left.leftRotate();
				//再对当前结点进行右旋转
				rightRotate();
			} else {
				//直接右旋转
				rightRotate();
			}
		}
        
    }

6.3测试

1661127313865

7.代码汇总

public class AVLTreeDemo {

	public static void main(String[] args) {
//		int[] arr = {4,3,6,5,7,8};
//		int[] arr = {10,1,8,9,7,6};
		int[] arr = {10,11,7,8,8,9};
		//创建一个AVLTree对象
		AVLTree avlTree = new AVLTree();
		//添加结点
		for(int i = 0; i<arr.length; i++){
			avlTree.add(new Node(arr[i]));
		}
		
		//中序遍历
		System.out.println("中序遍历之后");
		avlTree.infixOrder();
		
		System.out.println("平衡之后=====");
		System.out.println("树的高度=" + avlTree.getRoot().height());//3
		System.out.println("树的左子树高度=" + avlTree.getRoot().leftHeight());//2
		System.out.println("树的右子树高度=" + avlTree.getRoot().rightHeight());//2
		
		
		

	}

}

// 创建AVLTree
class AVLTree {
	private Node root;

	
	public Node getRoot() {
		return root;
	}

	public void setRoot(Node root) {
		this.root = root;
	}

	// 编写一个返回要删除结点右子树的最大值
	/**
	 * 
	 * @param node
	 *            传入的结点(当做二叉排序树的根结点)
	 * @return 返回以node为根结点的二叉排序树的最小结点的值
	 */
	public int delRightTreeMin(Node node) {
		Node target = node;
		// 循环的查找左子结点,就会找到最小值
		while (target.left != null) {
			target = target.left;
		}
		// 找到最小值之后,删除最小值
		delNode(target.value);
		// 此时target还是指向最小值结点的
		return target.value;
	}

	// 删除结点
	public void delNode(int value) {
		if (root == null) {
			return;
		} else {
			// 1.先查找要删除的结点
			Node targetNode = search(value);
			// 如果没有找到要删除的结点
			if (targetNode == null) {
				return;
			}
			// 如果发现当前这棵二叉排序树只有一个结点(特例,只有更结点)
			if (root.left == null && root.right == null) {
				root = null;
				return;
			}

			// 2.找到targetNode的父结点
			Node parent = searchParent(value);
			// 如果删除的结点是子结点
			if (targetNode.left == null && targetNode.right == null) {
				// 判断targetNode是父结点的左子结点还是右子结点
				if (parent.left != null && parent.left.value == value) {
					// 是左子结点
					parent.left = null;
				} else if (parent.right != null && parent.right.value == value) {
					// 是右子结点
					parent.right = null;
				}
			} else if (targetNode.right != null && targetNode.left != null) {
				// 删除有两棵子树的结点
				int minVal = delRightTreeMin(targetNode.right);
				targetNode.value = minVal;

			} else {// 删除只有一棵子树的结点

				if (targetNode.left != null) {// 如果删除的结点有左子结点
					if (parent != null) {
						// 如果targrtNode 是 parent 的左子结点
						if (parent.left.value == value) {
							parent.left = targetNode.left;
						} else {// 如果targrtNode 是 parent 的右子结点
							parent.right = targetNode.left;
						}
					} else {
						root = targetNode.left;
					}

				} else {// 如果删除的结点有右子结点
					if (parent != null) {
						// 如果targrtNode 是 parent 的左子结点
						if (parent.left.value == value) {
							parent.left = targetNode.right;
						} else {// 如果targrtNode 是 parent 的右子结点
							parent.right = targetNode.right;
						}
					} else {
						root = targetNode.right;
					}
				}
			}
		}
	}

	// 查找要删除的结点
	public Node search(int value) {
		if (root == null) {
			return null;
		} else {
			return root.search(value);
		}
	}

	// 查找要删除结点的父结点
	public Node searchParent(int value) {
		if (root == null) {
			return null;
		} else {
			return root.searchParent(value);
		}
	}

	// 添加结点方法
	public void add(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.add(node);
		}
	}

	// 中序遍历
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
		} else {
			System.out.println("二叉排序树为空,不能遍历");
		}
	}
}

// 第一,创建结点信息
class Node {
	int value;
	Node left;
	Node right;

	public Node(int value) {
		super();
		this.value = value;
	}

	// 返回左子树的高度
	public int leftHeight() {
		if (left == null) {
			return 0;
		}
		return left.height();
	}

	// 返回右子树的高度
	public int rightHeight() {
		if (right == null) {
			return 0;
		}
		return right.height();
	}

	// 返回以当前结点为根结点的高度,以该结点为根结点的树的高度
	public int height() {
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
	}
	
	// 左旋转方法
	public void leftRotate() {
		//创建新的结点,以当前根结点的值
		Node newNode = new Node(value);
		//把新的结点的左子树设置成当前结点的左子树
		newNode.left = left;
		//把新结点的右子树设置成当前结点的右子结点的左子树
		newNode.right = right.left;
		//把当前结点的值替换成当前结点的右子结点的值
		value = right.value;
		//把当前结点的右子树设置成当前结点的右子树的右子树
		right = right.right;//相当于跳过一个结点
		//把当前结点的左子树(左子结点)设置成新的结点
		left = newNode;		
	}
	
	//右旋转方法
	public void rightRotate(){
		//1.创建一个新结点newNode,新结点的值等于当前结点的值
		Node newNode = new Node(value);
		//2.把新结点的右子树设置成当前结点的右子树
		newNode.right = right;
		//3.把新结点的左子树设置成当前结点的左子树的右子树
		newNode.left = left.right;
		//4.把当前结点的值换成当前结点的左子结点
		value = left.value;
		//5.把当前结点的左子树设置成左子树的左子树
		left = left.left;
		//6.把当前结点的右子树设置成新结点(难)
		right = newNode;
	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	// 编写查找需要删除结点的父结点
	/**
	 * 
	 * @param value
	 *            要查找的结点值
	 * @return 返回的是要删除结点的父结点,如果没有就返回null
	 */
	public Node searchParent(int value) {
		// 如果当前结点就是要删除结点的父结点,返回该结点
		if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
			return this;
		} else {
			// 如果查找的值小于当前结点的值,并且当前结点的左子结点不为空
			if (value < this.value && this.left != null) {
				return this.left.searchParent(value);// 向左子树递归查找
			} else if (value >= this.value && this.right != null) {
				return this.right.searchParent(value);
			} else {
				return null;// 没有找到父结点
			}
		}

	}

	// 编写查找要删除的结点
	/**
	 * 
	 * @param value
	 *            需要删除的结点
	 * @return 如果找到则返回该结点,否则返回null
	 */
	public Node search(int value) {
		if (this.value == value) {
			// 找到删除的结点,返回
			return this;
		} else if (value < this.value) {
			// 如果查找的结点值小于当前结点,向左子树递归查找
			// 注意,判断左子结点是否为空
			if (this.left == null) {
				return null;// 没有找到
			}
			return this.left.search(value);
		} else {
			// 如果查找的结点值大于当前结点,向右子树递归查找
			// 注意,判断右子结点是否为空
			if (this.right == null) {
				return null;// 没有找到
			}
			return this.right.search(value);
		}

	}

	// 编写中序遍历方法(前序,后序遍历复习前面的)
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}

	}

	// 编写增加结点的方法
	public void add(Node node) {
		if (node == null) {
			return;
		}
		// 判断当前结点与左右子树值的大小关系
		if (node.value < this.value) {
			// 左子树的值小,向左子树增加
			if (this.left == null) {
				// 左子树为空,直接添加
				this.left = node;
			} else {
				// 左子树不为空,向左子树增加
				this.left.add(node);
			}
		} else {
			// 传入的node结点的值大于当前结点,增加到右子树
			if (this.right == null) {
				this.right = node;
			} else {
				// 递归增加到右子树
				this.right.add(node);
			}
		}
		
		//当添加完一个结点之后,如果 (右子树的高度-左子树的高度)> 1,则左旋转
		if (rightHeight() - leftHeight() > 1) {
			// 如果它的右子树的左子树的高度大于它的右子树的高度
			if (right != null && right.leftHeight() > right.rightHeight()) {
				// 先对当前结点的右节点(右子树)进行右旋转
				right.rightRotate();
				// 再对当前结点进行左旋转
				leftRotate();
			} else {
				// 直接左旋转
				leftRotate();
			}
			return;//必须要
		}
		
		// 当添加完一个结点之后,如果 (左子树的高度-右子树的高度)> 1,则右旋转
		if (leftHeight() - rightHeight()  > 1) {
			// 如果它的左子树的右子树的高度大于它的左子树的高度
			if (left != null && left.rightHeight() > left.leftHeight()) {
				//先对当前结点的左节点(左子树)进行左旋转
				left.leftRotate();
				//再对当前结点进行右旋转
				rightRotate();
			} else {
				//直接右旋转
				rightRotate();
			}
			
		}

	}

}

标签:左子,结点,right,右子,二叉树,平衡,null,left
From: https://www.cnblogs.com/y-tao/p/16611645.html

相关文章

  • 655. 输出二叉树
    655.输出二叉树给你一棵二叉树的根节点root,请你构造一个下标从0开始、大小为mxn的字符串矩阵res,用以表示树的格式化布局。构造此格式化布局矩阵需要遵循......
  • 后缀数组 & 后缀平衡树
    后缀数组&后缀平衡树PPT:【腾讯文档】后缀数组——钱贵宁后缀数组是什么本质上是对一个字符串的所有后缀进行排序例如字符串abbcaba,我们按长度顺序列出它的所有后......
  • 二叉树应用题
    1.非递归先序vector<int>preorderTraversal(TreeNode*root){vector<int>nums;stack<TreeNode*>s;while(root||!s.empty()){if(root){......
  • 二叉树遍历方法总结
    二叉树基本概念面试的时候提到的树,大部分都是二叉树.所谓二叉树是树的一种特殊结构,在二叉树中每个节点最多只能有两个子节点,在二叉树中最重要的操作莫过于遍历,即......
  • 数据结构3-二叉树
    二叉树概念  二叉树分类  二叉树遍历方式 ......
  • 大数据Hadoop之——Hadoop HDFS多目录磁盘扩展与数据平衡实战操作
    目录一、概述二、HadoopDataNode多目录磁盘配置1)配置hdfs-site.xml2)配置详解1、dfs.datanode.data.dir2、dfs.datanode.fsdataset.volume.choosing.policy3、dfs.datanod......
  • 102.binary-tree-level-order-traversal 二叉树的层序遍历
    利用queue先进先出的特性进行处理,利用queue.size()来识别元素是否在二叉树的同一层,同时要注意不能直接i<q.size()来判断,因为q.size()是不断变化的。classSolution{......
  • 107.binary-tree-level-order-traversal-ii 二叉树的层序遍历II
    参考102.binary-tree-level-order-traversal二叉树的层序遍历,翻转一下结果数组就好了。classSolution{public:vector<vector<int>>levelOrderBottom(TreeNode......
  • 【数据结构】红黑树与平衡二叉树的区别以及原理详解(附图解)
    引用网址:https://blog.csdn.net/weixin_44780082/article/details/112239269文章目录前言一、什么是红黑树1.1平衡二叉树1.2红黑树1.3平衡二叉树和红黑树的区别二、红黑......
  • 二叉树的统一迭代法遍历
    中序遍历中序遍历无法直接利用栈进行遍历,需要利用指针进行遍历,对栈中的节点进行操作。对于中间节点,如果指针遍历到了,但没有进行处理,就再push()一个nullptr,作为标记,说明这......