数据结构奇妙旅程之二叉平衡树

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱
ʕ̯•͡˔•̯᷅ʔ大家好，我是xiaoxie.希望你看完之后,有不足之处请多多谅解，让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN 如需转载还请通知˶⍤⃝˶
个人主页：xiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客
系列专栏：xiaoxie的JAVA系列专栏——CSDN博客●’ᴗ’σσணღ*
我的目标:”团团等我💪( ◡̀_◡́ ҂)” 

( ⸝⸝⸝›ᴥ‹⸝⸝⸝ )欢迎各位→点赞👍 + 收藏⭐️ + 留言📝​+关注（互三必回）!

一.二叉平衡树

1.二叉平衡树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

从上述概念以及图中可以看出，二叉搜索树具有以下特性：

1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧节点一定是树中最大的节点

2. 采用中序遍历遍历二叉搜索树，可以得到一个有序的序列 

2.二叉搜索树的主要操作

1. 查询

2.插入

1.插入的为一颗空树

直接插入即可

2.. 如果树不是空树，按照查找逻辑确定插入位置，插入新结点

根据二叉搜索树的性质插入节点,”左小右大“

1. 对于树中的任意节点 n，其左子树中的所有节点的值都小于 n 的值，其右子树中的所有节点的值都大于 n 的值。
2. 在插入新节点时，需要按照二叉搜索树的性质找到合适的位置插入，保持树的有序性。
3. 插入节点后，需要调整树的结构，保证树仍然是一个二叉搜索树。

3.删除

假设删除节点cur那么cur有以下几种情况

1.cur 的左孩子为空,右孩子不为空,

2.cur 的右孩子为空,左孩子不为空.

3.cur 的左右孩子均为空.

4.cur 的左右孩子均不为空.

接下来博主将会通过画图的形式来演示这四种情况该如何删除节点

1.cur 的左孩子为空,右孩子不为空

 2.cur 的右孩子为空,左孩子不为空.

3. cur 的左右孩子均为空.

4. cur 的左右孩子均不为空.

1.假设我们需要删除节点70,我们首先需要通过遍历二叉搜索树,找到70这个节点的对应位置.

2.我们发现70这个节点,左右孩子均不为空,这个时候就不可以通过简单的删除就可以了,我们需要用到替换法,即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被 删除节点中，再来处理该结点的删除问题.

2.1这里解释一下为什么是在它的右子树中寻找中序下的第一个结点(关键码最小),当需要删除一个节点时，如果该节点有右子树，则可以在右子树中找到中序遍历下的第一个节点（即右子树中最小的节点）来替代当前节点。这是因为右子树中的所有节点都大于当前节点，而右子树中最小的节点又小于右子树中的所有其他节点，所以用右子树中的最小节点来替代当前节点可以保持二叉搜索树的性质不变。

3.找到”替罪羊“节点 t 后我们就需要把要删除的节点cur使他的值等于t .

4.最后删除节点t即可.

4.二叉搜索树基本操作的Java代码实现

public class BinarySearchTree {
    public static class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public int val;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;
    /**
     * 查询节点是否存在
     * @author xiaoxie
     * @date 2024/3/6 10:44
     * @param val
     * @return boolean
     */
    public boolean search(int val) {
        if(root == null) {
            System.out.println();
            return false;
        }
        TreeNode cur = root;
        while (cur != null) {
            if(val < cur.val) {
                cur = cur.left;
            } else if (val > cur.val) {
                cur = cur.right;
            }else {
                System.out.println("找到了");
                return true;
            }
        }
        System.out.println("该节点"+val+"不存在");
        return false;
    }
    /**
     * 插入节点
     * @author xiaoxie
     * @date 2024/3/6 10:47
     * @param val
     */
    public void insertTreeNode(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(node.val < cur.val) {
                parent = cur;
                cur = cur.left;
            } else if (node.val > cur.val) {
                parent = cur;
                cur = cur.right;
            }else {
                System.out.println("节点值 " + val + " 已经存在于树中，不进行插入操作");
                return;
            }
        }
        //cur = null
        if(node.val < parent.val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
    }
    /**
     * 删除节点
     * 可以使用替罪羊的方法来实现
     * @author xiaoxie
     * @date 2024/3/6 12:15
     * @param val
     * @return boolean
     */
    public boolean remove(int val) {
        //首先先找到是哪一个节点
        if(root == null) {
            return false;
        }
        TreeNode parent = null;
        TreeNode cur = root;
        while (cur != null) {
            if(cur.val > val) {
                parent = cur;
                cur = cur.left;
            } else if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            }else {
                break;
            }
        }
        //cur == null 说明要删除的节点不在二叉搜索树上
        if(cur == null) {
            return false;
        }
        // cur有多种情况
        //1.cur 没有左右孩子
        //2.cur 只有左孩子
        //3.cur 只有右孩子

        //4.cur 有左右孩子 -- 需要使用替罪羊的方法来删除
        if(cur.right != null && cur.left != null) {
            TreeNode t = cur.right;
            TreeNode tp = cur;
            while (t.left != null) {
                tp = t;
                t = t.left;
            }
            cur.val = t.val;//使要删除的节点的值等于替罪羊节点
            //删除替罪羊节点
            if(tp.left == t) {
                tp.left = t.right;
            }else {//出现tp.right = t 的情况,t节点一开始就是叶子节点
                tp.right = t.right;
            }
        }else {
            //cur 只有右孩子
            if(cur.left == null && cur.right != null){
                if(parent == null) {
                    root = cur.right;
                }else {
                    if(parent.val < cur.val) {
                        parent.right = cur.right;
                    }else {
                        parent.left = cur.right;
                    }
                }
            }//cur 只有左孩子
            else if (cur.left != null && cur.right == null) {
                if(parent == null) {
                    root = cur.left;
                }else {
                    if(parent.val < cur.val) {
                        parent.right = cur.left;
                    }else {
                        parent.left = cur.left;
                    }
                }
            }
            //cur 没有左右孩子
            else  {
                if(parent == null) {
                    root = null;
                }else {
                    if(parent.val < cur.val) {
                        parent.right = null;
                    }else {
                        parent.left = null;
                    }
                }
            }
        }
        return true;
    }

 5.性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：

1.最优情况下，二叉搜索树为完全二叉树

其平均比较次数为：log N;

2.最差情况下，二叉搜索树退化为单支树

 其平均比较次数为: 2 / N

问题：如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插入关键码，都可以 是二叉搜索树的性能最佳？

那就需要用到AVL树了通过旋转来使二叉搜索树变成完全二叉树的形式,这里博主就不过多的赘述了,如果感兴趣,可以为博主点上一个关注,在下一篇文章中,博主将详细解读AVL树

感谢你的阅读!