二叉搜索树查询/插入/求前驱/求后继/删除-阿里云开发者社区

二叉搜索树查询/插入/求前驱/求后继/删除

2024-01-10 42

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 二叉搜索树查询/插入/求前驱/求后继/删除

二叉搜索树Binary Search Tree

二叉搜索树（Binary Search Tree)是一棵满足如下性质（BST性质）的二叉树:

任意结点的关键码≥它左子树中所有结点的关键码
任意结点的关键码≤它右子树中所有结点的关键码

根据以上性质，二叉搜索树的中序遍历必然为一个有序序列

BST–建立

为了避免越界，减少边界情况的特殊判断，一般在BST中额外插入两个保护结点

一个关键码为正无穷（一个很大的正整数)
一个关键码为负无穷

仅由这两个结点构成的BST就是一棵初始的空BST

BST–检索

检索关键码val是否存在

从根开始递归查找

若当前结点的关键码等于val，则已经找到
若关键码大于val，递归检索左子树（或不存在)
若关键码小于val，递归检索右子树（或不存在)

BST–插入

插入val与检索val的过程类似

若检索发现存在，则放弃插入（或者把val对应结点的计数+1，视要求而定)
若检索发现不存在（子树为空），直接在对应位置新建关键码为val的结点

BST –求前驱/后继

前驱:BST中小于val的最大结点

后继:BST中大于val的最小结点

求前驱和后继也是基于检索的，先检索val

以后继为例:

如果检索到了val，并且val存在右子树，则在右子树中一直往左走到底
否则说明没找到val或者val没有右子树，此时前驱就在检索过程经过的结点中(即当前结点的所有祖先节点，可以拿一个变量顺便求一下)

BST–删除

从BST中删除关键码为val的结点，可以基于检索＋求后继实现

首先检索val

如果val只有一棵子树，直接删除val，把子树和父结点相连就行了

如果有两棵子树，需要找到后继，先删除后继，再用后继结点代替val的位置

(因为后继是右子树一直往左走到底，所以它最多只会有一棵子树)

二叉搜索树Binary Search Tree

查询/插入/求前驱/求后继/删除操作的时间复杂度:

随机数据期望O(log N)

在非随机数据上，BST容易退化为O(N)，一般都要结合旋转操作来进行平衡

实战

701.二叉搜索树中的插入操作

https://leetcode.cn/problems/insert-into-a-binary-search-tree/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr) {
            return new TreeNode(val);
        }
        if(root->val < val){
            root->right = insertIntoBST(root->right,val);
        }else{
            root->left = insertIntoBST(root->left,val);
        }
        return root;
    }
};

面试题04.06.后继者

https://leetcode.cn/problems/successor-lcci/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        return getNext(root,p->val);
    }
    TreeNode* getNext(TreeNode* root, int val) {
        TreeNode* ans = nullptr;
        TreeNode* curr = root;
        while(curr != nullptr){
            if(curr->val == val) {
                if(curr->right != nullptr){
                    ans = curr->right;
                    while(ans->left !=nullptr) ans = ans->left;
                }
                break;
            }
            if(val < curr->val){
                if(ans == nullptr || ans->val > curr->val) ans = curr;
                curr = curr->left;
            }else {
                curr = curr->right;
            }
        }
        return ans;
    }
};

450.删除二叉搜索树中的节点

https://leetcode.cn/problems/delete-node-in-a-bst/

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr) return nullptr;
        if(root->val == key){
            if(root->left ==nullptr) return root->right;
            if(root->right == nullptr) return root->left;
            TreeNode *next = root->right;
            while(next->left != nullptr) next=next->left; 
            root->right=deleteNode(root->right,next->val);
            root->val = next->val;
            return root;
        }
        if(key < root->val){
            root->left=deleteNode(root->left,key);
        }else{
            root->right=deleteNode(root->right,key);
        }
        return root;
    }
};

538.把二叉搜索树转换为累加树

https://leetcode.cn/problems/convert-bst-to-greater-tree/

class Solution {
public:
    int sum = 0;
    TreeNode* convertBST(TreeNode* root) {
        if (root != nullptr) {
            convertBST(root->right);
            sum += root->val;
            root->val = sum;
            convertBST(root->left);
        }
        return root;
    }
};

推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

二叉搜索树查询/插入/求前驱/求后继/删除

二叉搜索树Binary Search Tree

BST–建立

BST–检索

BST–插入

BST –求前驱/后继

BST–删除

二叉搜索树Binary Search Tree

实战

热门文章

最新文章

相关电子书