二叉排序树转换为平衡二叉树

﹏ヽ暗。殇╰゛Y 2021-09-01 04:42 583阅读 0赞

# 二叉排序树的缺点 #

二叉排序树是在插入数据是一个一个对比然后进行插入，如果给出一串数字为\[1,2,3,4,5,6,7,8\]  
则它的排序结果为：这样的二叉树不仅性能会降低（没有链表存储的性能高），而且针对于增删查改都比较麻烦

# 平衡二叉树的概述 #

AVL树也叫平衡二叉树，如果一个树是平衡二叉树那么他也是一个二叉排序树。平衡二叉树分为：左旋转、右旋转以及双旋转  
特点：左子树和右子树的高度差的绝对值不超过1。

# 例： #

*  二叉排序树：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]
 *  构建平衡二叉树（右旋转）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]
 *  构建平衡二叉树（左旋转）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 2]
 *  平衡二叉树之双旋转  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 3]

# 代码实现 #

*  Node.java

public class Node {
       
       int value;
       Node left;
       Node right;
       
       public Node(int value) {
       	this.value = value;
       }
       /**
        * 返回当前节点的高度
        * @return
        */
       public int height() {
       	return Math.max(left==null?0:left.height(), right==null?0:right.height())+1;
       }
       /**
        * 获取左子树的高度
        * @return
        */
       public int leftHeight() {
       	if(left == null) {
       		return 0;
       	}
       	return left.height();
       }
       
       public int rightHeight() {
       	if(right == null) {
       		return 0;
       	}
       	return right.height();
       }
       /**
        * 向二叉排序树中添加节点
        * @param node
        */
       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 {
       		if(this.right == null) {
       			this.right = node;
       		}else {
       			this.right.add(node);
       		}
       	}
       	//查询是否平衡
       	//进行右旋转
       	if(leftHeight() - rightHeight()>=2) {
       		//双旋转
       		if(left != null && left.leftHeight()<left.rightHeight()) {
       			//先左旋转
       			left.leftRotate();
       			//在右旋转
       			rightRotate();
       		}else {
       			rightRotate();
       		}
       	}
       	//左旋转
       	if(leftHeight() - rightHeight()<=-2) {
       		//双旋转
       		if(right != null && right.rightHeight()<right.leftHeight()) {
       			right.leftRotate();
       			leftRotate();
       		//单旋转
       		}else {
       			leftRotate();
       		}
       	}
       }
       /**
        * 左旋转
        */
       private void leftRotate() {
       	Node newLeft = new Node(value);
       	newLeft.left = left;
       	newLeft.right = right.left;
       	value = right.value;
       	right = right.right;
       	left = newLeft;
       }
       /**
        * 右旋转
        */
       private void rightRotate() {
       	//创建一个新节点，值等于当前节点的值
       	Node newRight = new Node(value);
       	//把新节点的右子树设置为当前节点的右子树
       	newRight.right = right;
       	//把新节点左子树设置为当前节点的左子树的右子树
       	newRight.left = left.right;
       	//把当前节点的值换为左子节点的值
       	value = left.value;
       	//把当前节点的左子树设置为左子树的左子树
       	left = left.left;
       	//把当前节点的右子树设置为新节点
       	right = newRight;
       }
       /**
        * 中序遍历二叉树
        * @param node
        */
       public void midShow(Node node) {
       	if(node == null) {
       		return ;
       	}else {
       		midShow(node.left);
       		System.out.println(node.value);
       		midShow(node.right);
       	}
       }
       public Node search(int value) {
       	if(this.value == value) {
       		return this;
       	}else if(this.value > value) {
       		if(left == null) {
       			return null;
       		}
       		return left.search(value);
       	}else {
       		if(right == null) {
       			return null;
       		}
       		return right.search(value);
       	}
       }
       /**
        * 搜索父节点
        * @param value
        * @return
        */
       public Node searchParent(int value) {
       	if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
       		return this;
       	}else {
       		if(this.value > value && this.left != null) {
       			return this.left.searchParent(value);
       		}else if(this.value < value && this.left != null) {
       			return this.right.searchParent(value);
       		}
       		return null;
       	}
       }
    }

*  BinarySortTree.java

public class BinarySortTree {
       
       Node root;
       /**
        * 向二叉排序树中添加节点
        * @param node
        */
       public void add(Node node) {
       	if(root == null) {
       		root = node;
       	}else {
       		root.add(node);
       	}
       }
       /**
        * 中序遍历
        * @param node
        */
       public void midShow() {
       	if(root != null) {
       		root.midShow(root);
       	}
       }
       
       /**
        * 节点的查找
        * @param value
        * @return
        */
       public  Node search(int value) {
       	if(root == null) {
       		return null;
       	}else {
       		return root.search(value);
       	}
       }
    
       /**
        * 删除节点
        */
       public  void delete(int value) {
       	if(root == null) {
       		return ;
       	}else {
       		//找到这个节点
       		Node target = search(value);
       		//如果没有这个节点
       		if(target == null) {
       			return;
       		}
       		//找它的父节点
       		Node parent = searchParent(value);
       		//要删除节点的叶子节点
       		if(target.left == null && target.right == null) {
       			//要删除的节点时左子叶节点
       			if(parent.left.value == value) {
       				parent.left = null;
       			}else {
       				parent.right = null;
       		    }
       		//要删除的节点有两个子节点的情况
       		/**
       		 * 例如：要删除7，则要找到代替他的子树节点；
       		 * 这个节点一定是在右子树中存在，我们先删除右子树中的这个最小的值（即7的替换节点）并拿到他的值
       		 * 然后放到7的位置
       		 */
       		}else if(target.left != null && target.right != null) {
       			
       			//删除右子树中值最小的节点，并获取到该节点的值
       			 int min = deleteMin(target.right);
       			//替换目标节点中的值
       			 target.value = min;
       			 
       		//要删除的节点有一个左子节点或者右子节点
       		}else {
       			//有左子节点
       			if(target.left != null) {
       				//要删除的节点时父节点的左子节点
       				if(parent.left.value == value) {
       					parent.left = target.left;
       				}else {
       					parent.right = target.left;
       				}
       			//有右子节点
       			}else {
       				//要删除的节点时父节点的右子节点
       				if(parent.left.value == value) {
       					parent.left = target.right;
       				}else {
       					parent.right = target.right;
       				}
       			}
       		}
       	}
       }
       /**
        * 删除一颗树中最小的节点
        * @param right
        * @return
        */
       private int deleteMin(Node node) {
       	Node target = node;
       	//递归循环找右子树中最小的左子节点
       	while(target.left != null) {
       		target = target.left;
       	}
       	//如果最小的左子节点存在右子节点
       	delete(target.value);
       	return target.value;
       }
       /**
        * 搜索父节点
        * @param value
        * @return
        */
       public  Node searchParent(int value) {
       	if(root == null) {
       		return null;
       	}else {
       		return root.searchParent(value);
       	}
       }
    
    }

*  TestBinarySortTree

public class TestBinaryTree {
    
       public static void main(String[] args) {
       	
       	/**
       	 * 二叉排序树的优点在于： 插入很快，查找的性能相对来说比较高
       	 * 二叉排序树存在问题：
       	 * 	二叉排序树在插入数据的时候在进行一个一个的对比；但是对于一个单树而言，其性能还不如链表性能高
       	 * 平衡二叉树：要求左子树和右子树的高度差的绝对值不超过1，保证其查找效率高
       	 */
       	//右旋转举例
    //		int[] arr = new int[]{8,9,6,7,5,4};
       	//左旋转举例
       	int[] arr = new int[]{2,1,4,3,5,6};
       	
       	//创建一个二叉排序树
       	BinarySortTree bst = new BinarySortTree();
       	//循环添加                                                                                 
       	for(int i : arr) {
       		bst.add(new Node(i));
       	}
       	//查看高度
       	System.out.println(bst.root.height());
       	//查看跟节点的值
       	System.out.println(bst.root.value);
       	//查看左子树高度
       	System.out.println(bst.root.leftHeight());
       	//查看右子树高度
       	System.out.println(bst.root.rightHeight());
       }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70]: /images/20210901/0f71dcb2acab41748a1d7413752fb834.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 1]: /images/20210901/eb9bda3c82f845ba954bbe47a3703e54.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 2]: /images/20210901/c5ab011429e84ca9ad00fbcf98b917f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDE5MTA1_size_16_color_FFFFFF_t_70 3]: /images/20210901/7b5ec779ba394175a0b824b26172c824.png