二叉排序树转换为平衡二叉树 ﹏ヽ暗。殇╰゛Y 2021-09-01 04:42 543阅读 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
还没有评论，来说两句吧...