专业网站定制团队,网域名解析ip查询,网站推广基本预算,免费的图库网站目录 前言一、定义二、基本操作三、时间复杂度分析四、变体五、动态图解六、代码模版七、经典例题[1.——700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/)代码题解 [2.——938. 二叉搜索树的范围和](https://leetcode.cn/problems/ra… 目录 前言一、定义二、基本操作三、时间复杂度分析四、变体五、动态图解六、代码模版七、经典例题[1.——700. 二叉搜索树中的搜索](https://leetcode.cn/problems/search-in-a-binary-search-tree/)代码题解 [2.——938. 二叉搜索树的范围和](https://leetcode.cn/problems/range-sum-of-bst/)代码题解 [3.——98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree/)代码题解 八、总结结语 前言
这一期我们一起来学习二叉搜索树。二叉搜索树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在每次查找操作后通过一系列旋转操作将查找路径上的节点重新组织成一条链使得下次查找更加高效。
五、动态图解
元素查找 元素插入
元素删除
中序遍历
六、代码模版
#includeiostream
using namespace std;templatetypename 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){}
};templatetypename T
class BinarySearchTree {
private:TreeNodeT* root;TreeNodeT* insertNode(TreeNodeT* node, T val);TreeNodeT* removeNode(TreeNodeT* node, T val);bool searchNode(TreeNodeT* node, T val);void inOrder(TreeNodeT* 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;}
};templatetypename T
BinarySearchTreeT::~BinarySearchTree() {while (root) {remove(root-val);//每次都把root节点删除每次删除都产生新的root节点}
}templatetypename T
TreeNodeT* BinarySearchTreeT::insertNode(TreeNodeT* node, T val) {if (!node) {return new TreeNodeT(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;//说明当前节点与插入节点的值一致返回该节点即可
}templatetypename T
TreeNodeT* BinarySearchTreeT::removeNode(TreeNodeT* 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) {//要删除的节点只有右节点TreeNodeT* rightChild node-right;//定义一个变量储存该节点右节点的树delete node;return rightChild;}else if (node-right NULL) {//与上同理TreeNodeT* leftChild node-left;delete node;return leftChild;}else {//如果左右节点都有TreeNodeT* replacement node-right;//从右子树中找值最小的节点while (replacement-left) {replacement replacement-left;}node-val replacement-val;//找到之后赋给该节点node-right removeNode(node-right, replacement-val);//最后在删除最小值的节点}}return node;
}templatetypename T
bool BinarySearchTreeT::searchNode(TreeNodeT* 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;
}templatetypename T
void BinarySearchTreeT::inOrder(TreeNodeT* node) {if (node) {//中序遍历inOrder(node-left);cout node-val ,;inOrder(node-right);}
}int main() {BinarySearchTreeint 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(rootNULL)return NULL;if(valroot-val)return searchBST(root-right,val);else if(root-valval)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(rootNULL)return 0;int sum0;if(root-vallowroot-valhigh){sumroot-val;}sumrangeSumBST(root-left,low,high);sumrangeSumBST(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 {vectorint 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 i1;iret.size();i){if(ret[i]ret[i-1])return false;}return true;}
};八、总结
二叉搜索树是一种简单而有效的数据结构适用于许多查找、插入和删除操作。然而其性能受树的高度影响因此在最坏情况下可能退化为链表。为了克服这一缺点可以使用平衡二叉搜索树等变体来确保操作的时间复杂度始终为 O(logn)。
结语
下期我会更新二叉搜索树的题库一共十多道希望大家看完之后能去多多刷题巩固和运用知识点敬请期待下期文章。 相信大家通过本期学习初步了解二叉树下期作品我会更新二叉树的十几道题库我们下期一起学习二叉树的实战应用。
