二叉搜索树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等技术内容，立即学习
