您当前的位置:首页 > 电脑百科 > 程序开发 > 架构

一篇文章,带你快速读懂~数据结构之平衡查找树

时间:2019-12-16 11:24:32  来源:  作者:

平衡查找树

AVL树

在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

特点

AVL树本质上还是一棵二叉搜索树,它的特点是: [1]

1.本身首先是一棵二叉搜索树。

2.带有平衡条件:每个结点的左右子树的高度之差的绝对值(平衡因子)最多为1。

也就是说,AVL树,本质上是带了平衡功能的二叉查找树(二叉排序树,二叉搜索树)。

单旋转

右旋转
「五分钟」一篇文章,带你快速读懂~数据结构之平衡查找树

 

 

思路分析:

1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点

2、把新节点的右子树设置为当前节点的右子树

3、把新节点的左子树设置为当前节点的左子树的右子树

4、把当前节点的值换为左子节点的值

5、把当前节点的左子树设置为左子树的左子树

6、把当前节点的右子树设置为新节点

 

代码实现:

/**   
		 * @Title: rotateRight   
		 * @Description:右旋操作
		 * 	1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
		 * 	2、把新节点的右子树设置为当前节点的右子树
		 * 	3、把新节点的左子树设置为当前节点的左子树的右子树
		 * 	4、把当前节点的值换位左子节点的值
		 * 	5、把当前节点的左子树设置为左子树的左子树
		 * 	6、把当前节点的右子树设置为新节点    
		 * @param:       
		 * @return: void      
		 * @throws   
		 */
		private void rotateRight() {
			//1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
			Node tempNode = new Node(data);
			//2、把新节点的右子树设置为当前节点的右子树
			tempNode.right = right;
			//3、把新节点的左子树设置为当前节点的左子树的右子树
			tempNode.left = left.right;
			//4、把当前节点的值换位左子节点的值
			data = left.data;
			//5、把当前节点的左子树设置为左子树的左子树
			left = left.left;
			//6、把当前节点的右子树设置为新节点 
			right = tempNode;
		}

 

左旋转
「五分钟」一篇文章,带你快速读懂~数据结构之平衡查找树

 

 

思路分析:

1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点

2、把新节点的左子树设置为当前节点的左子树

3、把新节点的右子树设置为当前节点的右子树的左子树

4、把当前节点的值替换为右子节点的值

5、把当前节点的右子树设置为右子树的右子树

6、把当前节点的左子树设置为新节点

 

代码实现:

/**   
		 * @Title: rotateLeft   
		 * @Description:左旋操作:
		 * 	1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
		 * 	2、把新节点的左子树设置为当前节点的左子树
		 * 	3、把新节点的右子树设置为当前节点的右子树的左子树
		 * 	4、把当前节点的值替换为右子节点的值
		 * 	5、把当前节点的右子树设置为右子树的右子树
		 * 	6、把当前节点的左子树设置为新节点    
		 * @param:       
		 * @return: void      
		 * @throws   
		 */
		private void rotateLeft() {
			System.out.println("旋转代码中的 data = " + data);
			//以根节点为参考,创建新的节点
			Node tempNode = new Node(data);
			//把新节点的左子树设置为当前节点的左子树
			tempNode.setLeft(left);
			//把新节点的右子树设置为当前节点的右子树的左子树
			tempNode.setRight(right.left);
			//把当前节点的值替换为右子树的值
			data = right.data;
			//把当前节点的右子树设置为当前节点右子树的右子树
			right = right.right;
			//把当前节点的左子树设置为新节点
			left = tempNode;
		}

 

双旋转

右-左双旋转
「五分钟」一篇文章,带你快速读懂~数据结构之平衡查找树

 

//先对当前节点的右孩子右旋

right.rotateRight();

//再进行左旋操作

rotateLeft();

 

左-右双旋转
「五分钟」一篇文章,带你快速读懂~数据结构之平衡查找树

 


「五分钟」一篇文章,带你快速读懂~数据结构之平衡查找树

 

 

//先对当前节点的左孩子进行左旋

left.rotateLeft();

//再进行右旋

rotateRight();

实现

 

平衡二叉树实现增加旋转功能完整代码如下:

/**  
 * All rights Reserved, Designed By https://www.tulingxueyuan.com/
 * @Title:  AVLTree.JAVA   
 * @Package com.tuling.tree   
 * @Description:      
 * @author: 小白     
 * @Date 2019年12月8日 下午10:09:37   
 * @version V1.0 
 * @Copyright: 
 */ 
package com.tuling.tree;

/**
 * @ClassName AVLTree
 * @Description 
 * @Author 北京图灵学院
 * @Date 2019年12月8日 下午10:09:37
 */
public class AVLTree {
	
	private Node root;
	
	
	/**
	 * 
	 * @Title: add   
	 * @Description:    
	 * @param: @param data      
	 * @return: void      
	 * @throws
	 */
	public void add(int data) {
		System.out.print("当前添加数据:" + data + "    ");
		if(root == null) {
			root = new Node(data);
		}else {
			root.add(data);
		}
	}
	
	/**   
	 * @Title: rotateLeft   
	 * @Description:左旋操作    
	 * @param: node      
	 * @return: void      
	 * @throws   
	 */
	private Node rotateLeft(Node nodeN) {
		Node nodeC = nodeN.getRight();
		nodeN.setRight(nodeC.getLeft());
		nodeC.setLeft(nodeN);
		return nodeC;
	}
	
	public void inFixOrder() {
		if(root == null) {
			System.out.println("树为空!");
		}else {
			root.inFixOrder();
		}
	}

	public Node getRoot() {
		return root;
	}

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

	class Node{
		private Node left,right;
		private int data;
		/**   
		 * @Title:  Node   
		 * @Description:    
		 * @param:  @param data  
		 * @throws   
		 */  
		public Node(int data) {
			this.data = data;
		}

		/**   
		 * @Title: add   
		 * @Description:    
		 * @param: data      
		 * @return: void      
		 * @throws   
		 */
		public void add(int data) {
			if(this.data > data) {
				if(this.left == null) {
					this.left = new Node(data);
				}else {
					this.left.add(data);
				}
			}else if(this.data < data) {
				if(this.right == null) {
					this.right = new Node(data);
				}else {
					this.right.add(data);
				}
			}
			//TODO:
			//做完添加操作,
			
			if(leftHeight() - rightHeight() > 1) {//如果左子树的高度大于右子树的高度,需要右旋操作。
				if(left!=null && this.left.rightHeight()>left.leftHeight()) {
					System.out.print("左旋再右旋 -- " + left.data);
					//先对当前节点的左孩子进行左旋
					left.rotateLeft();
					//再进行右旋
					rotateRight();
				}else {
					System.out.print("右旋" + data);
					//直接右旋即可
					rotateRight();
				}
				
			}
			
			if(rightHeight() - leftHeight() > 1) {//如果右子树的高度大于左子树的高度,需要左旋操作
				if(right!=null && right.leftHeight()>right.rightHeight()) {
					System.out.print("右旋再左旋  -- " + right.data );
					//先对象当前节点的右孩子右旋
					right.rotateRight();
					//再进行左旋操作
					rotateLeft();
				}else {
					System.out.print("左旋  -- " + data);
					//直接左旋节课
					rotateLeft();
				}
			}
			
		}

		/**   
		 * @Title: rotateRight   
		 * @Description:右旋操作
		 * 	1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
		 * 	2、把新节点的右子树设置为当前节点的右子树
		 * 	3、把新节点的左子树设置为当前节点的左子树的右子树
		 * 	4、把当前节点的值换位左子节点的值
		 * 	5、把当前节点的左子树设置为左子树的左子树
		 * 	6、把当前节点的右子树设置为新节点    
		 * @param:       
		 * @return: void      
		 * @throws   
		 */
		private void rotateRight() {
			//1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
			Node tempNode = new Node(data);
			//2、把新节点的右子树设置为当前节点的右子树
			tempNode.right = right;
			//3、把新节点的左子树设置为当前节点的左子树的右子树
			tempNode.left = left.right;
			//4、把当前节点的值换位左子节点的值
			data = left.data;
			//5、把当前节点的左子树设置为左子树的左子树
			left = left.left;
			//6、把当前节点的右子树设置为新节点 
			right = tempNode;
		}

		/**   
		 * @Title: rotateLeft   
		 * @Description:左旋操作:
		 * 	1、回溯找到失去平衡的节点,以该节点为根,创建一个新节点
		 * 	2、把新节点的左子树设置为当前节点的左子树
		 * 	3、把新节点的右子树设置为当前节点的右子树的左子树
		 * 	4、把当前节点的值替换为右子节点的值
		 * 	5、把当前节点的右子树设置为右子树的右子树
		 * 	6、把当前节点的左子树设置为新节点    
		 * @param:       
		 * @return: void      
		 * @throws   
		 */
		private void rotateLeft() {
			System.out.println("旋转代码中的 data = " + data);
			//以根节点为参考,创建新的节点
			Node tempNode = new Node(data);
			//把新节点的左子树设置为当前节点的左子树
			tempNode.setLeft(left);
			//把新节点的右子树设置为当前节点的右子树的左子树
			tempNode.setRight(right.left);
			//把当前节点的值替换为右子树的值
			data = right.data;
			//把当前节点的右子树设置为当前节点右子树的右子树
			right = right.right;
			//把当前节点的左子树设置为新节点
			left = tempNode;
		}

		/**   
		 * @Title: rightHeight   
		 * @Description:    
		 * @param: @return      
		 * @return: int      
		 * @throws   
		 */
		private int rightHeight() {
			if(right == null) {
				return 0;
			}
			return height(right);
		}

		/**   
		 * @Title: height   
		 * @Description:    
		 * @param:      
		 * @return: int      
		 * @throws   
		 */
		private int height(Node node) {
			if(node == null) return 0;
			return 1+Math.max(height(node.left), height(node.right));
		}

		/**   
		 * @Title: leftHeight   
		 * @Description:    
		 * @param: @return      
		 * @return: int      
		 * @throws   
		 */
		private int leftHeight() {
			if(left == null)return 0;
			return height(left);
		}

		/**   
		 * @Title: inFixOrder   
		 * @Description:    
		 * @param:       
		 * @return: void      
		 * @throws   
		 */
		public void inFixOrder() {
			if(this.left!=null) {
				this.left.inFixOrder();
			}
			System.out.println(this.data);
			if(this.right!=null) {
				this.right.inFixOrder();
			}
		}

		public Node getLeft() {
			return left;
		}

		public void setLeft(Node left) {
			this.left = left;
		}

		public Node getRight() {
			return right;
		}

		public void setRight(Node right) {
			this.right = right;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

	}
}


Tags:平衡查找树   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
平衡查找树AVL树在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次...【详细内容】
2019-12-16  Tags: 平衡查找树  点击:(79)  评论:(0)  加入收藏
▌简易百科推荐
为了构建高并发、高可用的系统架构,压测、容量预估必不可少,在发现系统瓶颈后,需要有针对性地扩容、优化。结合楼主的经验和知识,本文做一个简单的总结,欢迎探讨。1、QPS保障目标...【详细内容】
2021-12-27  大数据架构师    Tags:架构   点击:(5)  评论:(0)  加入收藏
前言 单片机开发中,我们往往首先接触裸机系统,然后到RTOS,那么它们的软件架构是什么?这是我们开发人员必须认真考虑的问题。在实际项目中,首先选择软件架构是非常重要的,接下来我...【详细内容】
2021-12-23  正点原子原子哥    Tags:架构   点击:(7)  评论:(0)  加入收藏
现有数据架构难以支撑现代化应用的实现。 随着云计算产业的快速崛起,带动着各行各业开始自己的基于云的业务创新和信息架构现代化,云计算的可靠性、灵活性、按需计费的高性价...【详细内容】
2021-12-22    CSDN  Tags:数据架构   点击:(10)  评论:(0)  加入收藏
▶ 企业级项目结构封装释义 如果你刚毕业,作为Java新手程序员进入一家企业,拿到代码之后,你有什么感觉呢?如果你没有听过多模块、分布式这类的概念,那么多半会傻眼。为什么一个项...【详细内容】
2021-12-20  蜗牛学苑    Tags:微服务   点击:(9)  评论:(0)  加入收藏
我是一名程序员关注我们吧,我们会多多分享技术和资源。进来的朋友,可以多了解下青锋的产品,已开源多个产品的架构版本。Thymeleaf版(开源)1、采用技术: springboot、layui、Thymel...【详细内容】
2021-12-14  青锋爱编程    Tags:后台架构   点击:(21)  评论:(0)  加入收藏
在了解连接池之前,我们需要对长、短链接建立初步认识。我们都知道,网络通信大部分都是基于TCP/IP协议,数据传输之前,双方通过“三次握手”建立连接,当数据传输完成之后,又通过“四次挥手”释放连接,以下是“三次握手”与“四...【详细内容】
2021-12-14  架构即人生    Tags:连接池   点击:(17)  评论:(0)  加入收藏
随着移动互联网技术的快速发展,在新业务、新领域、新场景的驱动下,基于传统大型机的服务部署方式,不仅难以适应快速增长的业务需求,而且持续耗费高昂的成本,从而使得各大生产厂商...【详细内容】
2021-12-08  架构驿站    Tags:分布式系统   点击:(23)  评论:(0)  加入收藏
本系列为 Netty 学习笔记,本篇介绍总结Java NIO 网络编程。Netty 作为一个异步的、事件驱动的网络应用程序框架,也是基于NIO的客户、服务器端的编程框架。其对 Java NIO 底层...【详细内容】
2021-12-07  大数据架构师    Tags:Netty   点击:(17)  评论:(0)  加入收藏
前面谈过很多关于数字化转型,云原生,微服务方面的文章。虽然自己一直做大集团的SOA集成平台咨询规划和建设项目,但是当前传统企业数字化转型,国产化和自主可控,云原生,微服务是不...【详细内容】
2021-12-06  人月聊IT    Tags:架构   点击:(23)  评论:(0)  加入收藏
微服务看似是完美的解决方案。从理论上来说,微服务提高了开发速度,而且还可以单独扩展应用的某个部分。但实际上,微服务带有一定的隐形成本。我认为,没有亲自动手构建微服务的经历,就无法真正了解其复杂性。...【详细内容】
2021-11-26  GreekDataGuy  CSDN  Tags:单体应用   点击:(35)  评论:(0)  加入收藏
相关文章
    无相关信息
最新更新
栏目热门
栏目头条