【数据结构】二叉搜索树的实现

水深无声 2024-04-17 10:36 64阅读 0赞

#### 文章目录 ####

*  ?二叉搜索树的概念
 *  ?二叉搜索树功能实现
 *   *  ?查找关键字key
     *   *  ?代码实现：
     *  ?插入关键字key
     *   *  ?代码实现：
     *  ?删除关键字key
     *   *  ?代码实现：
 *  ?搜索二叉树性能分析
 *  ⭕总结

## ?二叉搜索树的概念 ##

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

*  若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
 *  若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
 *  它的左右子树也分别为二叉搜索树

比如以下就为一个人二叉搜索树

int\[\] array =\{5,3,4,1,7,8,2,6,0,9\};  
![在这里插入图片描述][7b05835a54f749f8828c7a81f055550e.png]

## ?二叉搜索树功能实现 ##

我们创建一个二叉树如下所示，方便后续操作：

class TreeNode {
        
            public int key ;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int key) {
        
                this.key = key;
            }
        }
        public TreeNode root;//根节点

### ?查找关键字key ###

若根节点不为空：

*  如果根节点key==查找key，返回true
 *  如果根节点key > 查找key，在其左子树查找
 *  如果根节点key < 查找key，在其右子树查找

否则，返回false

![在这里插入图片描述][7183091406bf4e9a9cb46fb0d3e50475.png]

#### ?代码实现： ####

public Boolean find(int key) {
        
            TreeNode cur = root;
            while (cur != null) {
        
                if (key == cur.key) {
        
                    return true;
                } else if (key < cur.key) {
        
                    cur = cur.left;
                } else {
        
                    cur = cur.right;
                }
            }
            return false;
        }

### ?插入关键字key ###

插入操作可以分为以下两种情况：

1.  如果树为空树，即根 == null，直接插入![在这里插入图片描述][a389a79f194e4d6db0234a6019b7d22d.png]
2.  如果树不是空树，按照查找逻辑确定插入位置，插入新结点  
    ![在这里插入图片描述][9b2497784c0040e583323885d6a8c451.png]

#### ?代码实现： ####

public void insert(int key) {
        
            if(root == null) {
        
                root = new TreeNode(key);
                return;
            }
            TreeNode cur = root;
            TreeNode parent = null;
            while (cur != null) {
        
                if (key == cur.key) {
        
                    return ;
                } else if (key < cur.key) {
        
                    parent = cur;
                    cur = cur.left;
                } else {
        
                    parent = cur;
                    cur = cur.right;
                }
            }
            TreeNode node = new TreeNode(key);
            if (key < parent.key) {
        
                parent.left = node;
            } else {
        
                parent.right = node;
            }
        }

### ?删除关键字key ###

设待删除结点为 cur, 待删除结点的双亲结点为 parent，我们又可以分为四种情况

1.  cur.left == null

>  *  cur 是 root，则 root = cur.right
>  *  cur 不是 root，cur 是 parent.left，则 parent.left = cur.right
>  *  cur 不是 root，cur 是 parent.right，则 parent.right = cur.right

如下图所示：  
![在这里插入图片描述][e8bacb8cf4854087b1f78b27234c2bfb.png]

1.  cur.right == null

> 1.  cur 是 root，则 root = cur.left
> 2.  cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
> 3.  cur 不是 root，cur 是 parent.right，则 parent.right = cur.left

与·上述情况类似，不做过多赘述

1.  cur.left != null && cur.right != null

> 需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题

我们使用target来遍历寻找右子树中关键码最小的节点，targetParent用来记录target的父亲节点

找到相应节点后与待删除的cur节点的值进行替换

最后删除target结点即可

1.  cur左右孩子均不存在

> 直接置为null就好

#### ?代码实现： ####

private void removeNode(TreeNode parent, TreeNode cur) {
        
            if(cur.left == null) {
        
                if(cur == root) {
        
                    root = cur.right;
                }else if(parent.left == cur) {
        
                    parent.left = cur.right;
                }else {
        
                    parent.right = cur.right;
                }
            }else if(cur.right == null) {
        
                if(cur == root) {
        
                    root = cur.left;
                }else if(parent.left == cur) {
        
                    parent.left = cur.left;
                }else {
        
                    parent.right = cur.left;
                }
            }else {
        
                TreeNode target = cur.right;
                TreeNode targetParent = cur;
                while (target.left != null) {
        
                    targetParent = target;
                    target = target.left;
                }
                cur.key = target.key;
                if(target == targetParent.left) {
        
                    targetParent.left = target.right;
                }else {
        
                    targetParent.right = target.right;
                }
            }
        }

## ?搜索二叉树性能分析 ##

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。

对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：  
![在这里插入图片描述][aab40b2cc9284ee4b265d32d1165d7c9.png]  
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：  
![在这里插入图片描述][71b4c78d34424bc1a100e3090eb589b5.png]

最差情况下，二叉搜索树退化为单支树，其平均比较次数为：  
![在这里插入图片描述][40b7669dd2ff40b0aef011fcdf3bd768.png]

## ⭕总结 ##

关于《【数据结构】 二叉搜索树的实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[7b05835a54f749f8828c7a81f055550e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/8c3ecb46250446379acfe1c9f29000ca.png
[7183091406bf4e9a9cb46fb0d3e50475.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/250ccc16b36d44fb87a37336dc8b04b8.png
[a389a79f194e4d6db0234a6019b7d22d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9db5f38c67a44826a25772498f7da4f4.png
[9b2497784c0040e583323885d6a8c451.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/bfde9a10427e4abcb9ab751ec2337f8c.png
[e8bacb8cf4854087b1f78b27234c2bfb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ff06b26672d248469e54bb161a9ff776.png
[aab40b2cc9284ee4b265d32d1165d7c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/ace0a7cf6bb14cb89081ab66b2b6bf36.png
[71b4c78d34424bc1a100e3090eb589b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/caf8ca4afd18479ea24be53299b93dde.png
[40b7669dd2ff40b0aef011fcdf3bd768.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/aff1652a72514ba998bb912e68a8a77c.png