初级数据结构——二叉搜索树
目录
前言
这一期我们一起来学习二叉搜索树。二叉搜索树（Binary Search Tree, BST）是一种重要的数据结构，在计算机科学中广泛应用于查找、插入和删除操作。以下是对二叉搜索树的基本分析，包括其定义、性质、操作的时间复杂度以及一些变体。
一、定义
二叉搜索树是一种二叉树，其中每个节点包含一个键值，且满足以下性质：
左子树性质：左子树中所有节点的键值都小于根节点的键值。
右子树性质：右子树中所有节点的键值都大于根节点的键值。
递归性质：左子树和右子树本身也是二叉搜索树。
二、基本操作
1.查找（Search）
算法：从根节点开始，如果目标键值小于当前节点的键值，则递归地在左子树中查找；如果目标键值大于当前节点的键值，则递归地在右子树中查找；如果找到目标键值，则返回该节点。
时间复杂度：在最坏情况下（树退化为链表），时间复杂度为 O(n)；在最优情况下（树是平衡的），时间复杂度为 O(logn)。
2.插入（Insert）
算法：从根节点开始，找到合适的位置插入新节点。如果目标键值小于当前节点的键值，则递归地在左子树中查找插入位置；如果目标键值大于当前节点的键值，则递归地在右子树中查找插入位置；如果目标键值已经存在，则根据具体需求更新节点（例如，更新节点的值或不做任何操作）。
时间复杂度：与查找操作类似，最坏情况下为 O(n)，最优情况下为 O(logn)。
3.删除（Delete）
算法：找到要删除的节点，然后分三种情况处理：
叶子节点：直接删除。
只有一个子节点：用其子节点替代被删除节点。
有两个子节点：找到该节点的中序后继（或中序前驱），用其值替代被删除节点的值，然后递归删除中序后继（或中序前驱）。
时间复杂度：最坏情况下为 O(n)，最优情况下为 O(logn)。
三、时间复杂度分析
二叉搜索树的时间复杂度依赖于树的高度。在最坏情况下（树退化为链表），树的高度为 n，因此各种操作的时间复杂度均为 O(n)。然而，在最优情况下（树是平衡的），树的高度为 logn，因此各种操作的时间复杂度均为 O(logn)。
四、变体
为了改善二叉搜索树在最坏情况下的性能，人们提出了多种变体：
平衡二叉搜索树（Balanced BST）：如AVL树、红黑树等，通过维护树的平衡来确保操作的时间复杂度始终为 O(logn)。
B树（B-Tree）：一种自平衡的树，能够保持数据有序，其设计目的是减少磁盘I/O操作，广泛应用于数据库和文件系统。
伸展树（Splay Tree）：在每次查找操作后，通过一系列旋转操作将查找路径上的节点重新组织成一条链，使得下次查找更加高效。
五、动态图解
元素查找：
元素插入：
元素删除：
中序遍历
六、代码模版
#include<iostream>
using namespace std;
template<typename T>
struct TreeNode {
T val;
TreeNode* left;
TreeNode* right;
TreeNode(T x):val(x),left(NULL),right(NULL){}
TreeNode():val(0),left(NULL),right(NULL){}
};
template<typename T>
class BinarySearchTree {
private:
TreeNode<T>* root;
TreeNode<T>* insertNode(TreeNode<T>* node, T val);
TreeNode<T>* removeNode(TreeNode<T>* node, T val);
bool searchNode(TreeNode<T>* node, T val);
void inOrder(TreeNode<T>* node);
public:
BinarySearchTree():root(NULL){}
~BinarySearchTree();
void insert(T val) {
root = insertNode(root, val);
}
void remove(T val) {
root = removeNode(root, val);
}
bool search(T val) {
return searchNode(root, val);
}
void inOrderTraversal() {
inOrder(root);
cout << endl;
}
};
template<typename T>
BinarySearchTree<T>::~BinarySearchTree() {
while (root) {
remove(root->val);//每次都把root节点删除，每次删除都产生新的root节点
}
}
template<typename T>
TreeNode<T>* BinarySearchTree<T>::insertNode(TreeNode<T>* node, T val) {
if (!node) {
return new TreeNode<T>(val);//递归出口，该节点为空时就说明插入到当前位置，定义新的变量接收val
}
if (node->val > val) {
node->left = insertNode(node->left, val);
}
else if (node->val < val) {
node->right = insertNode(node->right, val);
}
return node;//说明当前节点与插入节点的值一致返回该节点即可
}
template<typename T>
TreeNode<T>* BinarySearchTree<T>::removeNode(TreeNode<T>* node, T val) {
if (!node)return NULL;//递归出口，如果找完了整棵树都没找到该值就返回NULL
if (node->val > val) node->left = removeNode(node->left, val);
else if (node->val < val)node->right = removeNode(node->right, val);
else {//该节点的值等于要删除节点的值一致就说明找到了
if (node->left == NULL && node->right == NULL) {//如果该节点为叶子结点，接直接删除该节点就行
delete node;
return NULL;//因为删除了该节点所以它就为空了返回即可
}
else if (node->left == NULL) {//要删除的节点只有右节点
TreeNode<T>* rightChild = node->right;//定义一个变量储存该节点右节点的树
delete node;
return rightChild;
}
else if (node->right == NULL) {//与上同理
TreeNode<T>* leftChild = node->left;
delete node;
return leftChild;
}
else {//如果左右节点都有
TreeNode<T>* replacement = node->right;//从右子树中找值最小的节点
while (replacement->left) {
replacement = replacement->left;
}
node->val = replacement->val;//找到之后赋给该节点
node->right = removeNode(node->right, replacement->val);//最后在删除最小值的节点
}
}
return node;
}
template<typename T>
bool BinarySearchTree<T>::searchNode(TreeNode<T>* node, T val) {
if (!node)return false;//递归出口如果找完了整棵树都没找到该值就返回false
if (val < node->val) {//递归查找如果要查找的值小于当前节点那么就继续递归找左节点
return searchNode(node->left, val);
}
else if (val > node->val) return searchNode(node->right, val);//与上同理
return true;
}
template<typename T>
void BinarySearchTree<T>::inOrder(TreeNode<T>* node) {
if (node) {//中序遍历
inOrder(node->left);
cout << node->val << ',';
inOrder(node->right);
}
}
int main() {
BinarySearchTree<int> bst;
bst.insert(30);
bst.insert(10);
bst.insert(20);
bst.insert(40);
bst.insert(90);
bst.insert(69);
bst.inOrderTraversal();//中序遍历为递增有序的数列
bst.remove(40);
bst.inOrderTraversal();
return 0;
}
七、经典例题
1.——700. 二叉搜索树中的搜索
（蓝色字体可以点进去看原题）
代码题解
/**
* 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* searchBST(TreeNode* root, int val) {
if(root==NULL)return NULL;
if(val>root->val)return searchBST(root->right,val);
else if(root->val>val)return searchBST(root->left,val);
return root;
}
};
2.——938. 二叉搜索树的范围和
代码题解
/**
* 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:
int rangeSumBST(TreeNode* root, int low, int high) {
if(root==NULL)return 0;
int sum=0;
if(root->val>=low&&root->val<=high){
sum+=root->val;
}
sum+=rangeSumBST(root->left,low,high);
sum+=rangeSumBST(root->right,low,high);
return sum;
}
};
3.——98. 验证二叉搜索树
代码题解
/**
* 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 {
vector<int> ret;
void inOrder(TreeNode*root){
if(root){
inOrder(root->left);
ret.push_back(root->val);
inOrder(root->right);
}
}
public:
bool isValidBST(TreeNode* root) {
ret.clear();
inOrder(root);//中序遍历之后就是递增的数列
for(int i=1;i<ret.size();i++){
if(ret[i]<=ret[i-1])return false;
}
return true;
}
};
八、总结
二叉搜索树是一种简单而有效的数据结构，适用于许多查找、插入和删除操作。然而，其性能受树的高度影响，因此在最坏情况下可能退化为链表。为了克服这一缺点，可以使用平衡二叉搜索树等变体来确保操作的时间复杂度始终为 O(logn)。
结语
下期我会更新二叉搜索树的题库一共十多道，希望大家看完之后能去多多刷题巩固和运用知识点，敬请期待下期文章。
相信大家通过本期学习初步了解二叉树，下期作品我会更新二叉树的十几道题库，我们下期一起学习二叉树的实战应用。
原文地址：https://blog.csdn.net/ycs66/article/details/144089361
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！