平衡二叉搜索树的创建

╰半橙微兮° 2023-07-10 15:34 8阅读 0赞

### 平衡二叉搜索树 ###

**平衡二叉树**：每个结点的左右子树高度差不超过1，左右子树均为平衡二叉树  
**搜索二叉树**：左结点 < 根结点 <右结点  
平衡二叉搜索树则是优化后的搜索二叉树，使得查找的效率提升，但是在添加数据时，需要进行复杂的判断，所以一般使用在**查找频繁**而**修改很少**的存储结构中。

### 平衡二叉树的建立 ###

整个建立过程分为三大部分：  
①插入新的结点  
②判断插入结点后树是否平衡，并找到不平衡的点  
③若不平衡，判断旋转方向，进行调整

##### 插入新的结点 #####

这一个步骤较为容易实现，按照搜索二叉树的性质：将数据与结点数据进行比较，小于走左树，大于走右树，直到走到叶子结点，建立新结点，将数据进行插入。

##### 判断新树的平衡，并找到不平衡的点 #####

不平衡的点即需要进行旋转调整的点，这时就有一个问题：如果根结点和子树同时变为不平衡状态，那么应该调整哪个点？  
我的想法：由于整个树的添加和变化是一个动态规划的过程，每一步的变动都会影响下一步。当新结点的加入只有两种情况：  
①根和子树都不平衡时，先调整子树使其到达平衡状态，此时根也会随着子树变得平衡。  
②根不平衡，直接调整根。

关于不平衡点的定位：不平衡的点只出现在添加数据时所途径的点，所以使用栈将其进行存储，再出栈进行判断。

##### 判断旋转方向，进行调整 #####

树的旋转有四种，每一种方式都针对着不同的非平衡状态。所以，需判断以不平衡结点为根的树的结构。  
其实，对于每一种旋转（RR、LL、RL、LR）都指的是从根结点到破坏结点是所走结点的方向（R指左子树，L指右子树），而且只需判断前两步即可。  
此时，判断方向也需要借助于栈中存储的途径结点：在回溯判断是否平衡时，记录路径，用以判断旋转方向。

### 实际建立过程 ###

##### 插入结点 #####

/**
      * 添加新结点
      * @param data  数据
      * @param sBalance  栈
      * @return 新结点
      */
     private TreeNode addNewData(String data,StackBalance sBalance){  
      	//遍历树，找到位置添加
      	TreeNode moveNode = this.rootNode;
      	int numData = Integer.parseInt(data);
      	while(moveNode != null) {
       		sBalance.pop(moveNode);            //存储遍历结点的父结点
       		if(numData < Integer.parseInt(moveNode.getData())) {
        			moveNode = moveNode.getLeChild();
       		}else {
        			moveNode = moveNode.getRiChild();
       		}   
      	}
      	TreeNode midNode = new TreeNode();
     	midNode.setData(data);
      	//判断为左孩子还是右孩子
      	TreeNode parNode = sBalance.seekTop();
      	if(numData < Integer.parseInt(parNode.getData())){
       		parNode.setLeChild(midNode);
      	}else {
       		parNode.setRiChild(midNode);
      	} 
      	return midNode;
     }

##### 判断是否平衡 #####

用到了我之前写的平衡函数：BalanceJudge.optiBalance(parNode, depth)

/**
      * 是否平衡，不平衡并返回该结点，平衡返回null
      * @param sBalance 栈
      * @param midNode 新加结点
      * @param track 路径
      * @return 不平衡结点
      */
     private TreeNode ifBalance(StackBalance sBalance, TreeNode midNode,char track[]) {
      	//判断树是否平衡，不平衡进行旋转
      	//依靠栈中元素，逐步出栈判断父结点的平衡状态
      	int depth[] = new int[1];
      	TreeNode sonNode = midNode;
     	TreeNode parNode = sBalance.push();
      	while(BalanceJudge.optiBalance(parNode, depth)) {
       		//当当前结点平衡时，记录到添加结点的路径
       		if(parNode.getLeChild() == sonNode) {
        			track[1] = track[0];
        			track[0] = 'l';
       		}else {
        			track[1] = track[0];
        			track[0] = 'r';
       		}
       		if(!sBalance.ifEmpty()) {
        			sonNode = parNode;
        			parNode = sBalance.push();
       		}else {
        			break;
       		}    
      	}
     	 //不平衡记录
      	if(BalanceJudge.optiBalance(parNode, depth)) {
        		if(parNode.getLeChild() == sonNode) {
        			track[1] = track[0];
        			track[0] = 'l';
       		}else {
        			track[1] = track[0];
        			track[0] = 'r';
       		}
       		return parNode; 
      	} 
      	return null;
     }

##### 对不平衡结点进行旋转 #####

用到了我之前写的旋转函数：BalanceSpin.LLSpin(unBalance)、BalanceSpin.LLSpin(unBalance)、BalanceSpin.LLSpin(unBalance)、BalanceSpin.LLSpin(unBalance)

/**
      * 对不平衡结点进行旋转
      * @param sBalance 栈
      * @param unBalance 不平衡结点
      * @param track 路径
      */
     private void treeSpin(StackBalance sBalance,TreeNode unBalance,char track[]) {  
      	TreeNode afSpinNode = null; //记录旋转后不平衡子树的根结点
      	if(track[0] == 'l' && track[1] == 'l') {
       		afSpinNode = BalanceSpin.LLSpin(unBalance);
       		System.out.println(" LL型旋转");
      	}else if(track[0] == 'r' && track[1] == 'r') {
       		afSpinNode = BalanceSpin.RRSpin(unBalance);
       		System.out.println(" RR型旋转");
      	}else if(track[0] == 'l' && track[1] == 'r') {
       		afSpinNode = BalanceSpin.LRSpin(unBalance);
       		System.out.println(" LR型旋转");
      	}else if(track[0] == 'r' && track[1] == 'l') {
       		afSpinNode = BalanceSpin.RLSpin(unBalance);
       		System.out.println(" RL型旋转");
      	}
      	//判断是否为根结点，若不是则要更改父结点处的引用
      	if(unBalance != this.rootNode) {
       		TreeNode faNode = sBalance.push(); //取出父结点
       		//判断左右孩子
      	 	if(faNode.getLeChild() == unBalance) {
        			faNode.setLeChild(afSpinNode);
       		}else {
        			faNode.setRiChild(afSpinNode);
       		}
      	}else {
       		this.rootNode = afSpinNode;
      	}
     }

PS：我此处没设置，数据相等时怎么办，可以在插入数据时添加等号进行判断

##### 主函数（将之前几个函数统一起来） #####

/**
      * 根据文件内容建立一个平衡二叉树
      * @param file 文件名
      * @return   根结点
      */
     public TreeNode file2BalanceTree(String file) {
      	try {
       		BufferedReader bReader = new BufferedReader(new FileReader(file));
       		StackBalance sBalance = new StackBalance();
       		String data = bReader.readLine();
       		//根结点
       		if(this.rootNode == null) {
        			this.rootNode = new TreeNode();
        			this.rootNode.setData(data);  
       		}  
       		while((data = bReader.readLine()) != null) {
        			//添加新结点
        			TreeNode midNode = addNewData(data, sBalance);    
        			//判断平衡
        			char[] track = new char[2];  //记录两步用以判断旋转方向
        			TreeNode unBalance = ifBalance(sBalance, midNode, track);
        			//当前结点不平衡,旋转   
        			if(unBalance != null) { 
         				System.out.print("插入数据："+midNode.getData()+"时，导致结点：");
         				System.out.print(unBalance.getData()+"不平衡");
         				treeSpin(sBalance, unBalance, track);   
        			}     
       		}     
       		bReader.close();
      	} catch (Exception e) {
       		e.printStackTrace();
      	}
      		return this.rootNode;
     }

##### 测试结果 #####

①单旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]  
②双旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200303160555484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200303160618697.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70