初级数据结构——二叉搜索树

前言

这一期我们一起来学习二叉搜索树。二叉搜索树（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;//递归出口，如果找完了整棵树都没找到该值就返回NULLif (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;//递归出口如果找完了整棵树都没找到该值就返回falseif (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)。

结语

下期我会更新二叉搜索树的题库一共十多道，希望大家看完之后能去多多刷题巩固和运用知识点，敬请期待下期文章。

相信大家通过本期学习初步了解二叉树，下期作品我会更新二叉树的十几道题库，我们下期一起学习二叉树的实战应用。