当前位置： 首页 > article >正文

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

article 2024/12/2 22:41:19

目录

  • 前言
  • 一、定义
  • 二、基本操作
  • 三、时间复杂度分析
  • 四、变体
  • 五、动态图解
  • 六、代码模版
  • 七、经典例题
    • [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）：在每次查找操作后，通过一系列旋转操作将查找路径上的节点重新组织成一条链，使得下次查找更加高效。

五、动态图解

元素查找：
在这里插入图片描述
元素插入：
在这里插入图片描述

元素删除：
元素

中序遍历
在这里插入图片描述

六、代码模版

#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)。

结语

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

在这里插入图片描述

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


http://www.kler.cn/a/419052.html

相关文章：

  • openjdk17 jvm堆空间分配
  • 使用OSPF配置不同进程的中小型网络
  • 架构师：Dubbo 服务请求失败处理的实践指南
  • 视觉语言动作模型VLA的持续升级：从π0之参考基线Octo到OpenVLA、TinyVLA、DeeR-VLA、3D-VLA
  • ffmpeg安装(windows)
  • Observability：如何在 Kubernetes pod 中轻松添加应用程序监控
  • 【Linux】MDNS：局域网域名解析
  • 网络安全之IP伪造
  • 【k8s】kubelet 的相关证书
  • java并发面试复习
  • MyBlog(五) -- 用户注册页面完善
  • 群控系统服务端开发模式-应用开发-短信工厂结构封装
  • Harmony NEXT-越过相机读写权限上传图片至项目云存储中
  • Solidity基础语法
  • 纯Go语言开发人脸检测、瞳孔/眼睛定位与面部特征检测插件-助力GoFly快速开发框架
  • js对于json的序列化、反序列化有哪几种方法
  • 计算机网络基础篇
  • idea 自动导包，并且禁止自动导 *（java.io.*）
  • 数据结构之堆：原理与实现
  • 《Python基础》之类的定义、封装、继承
  • ubuntu 安装docker-compose
  • PHP操作redis删除指定前缀的key值
  • Apache storm安装教程（单机版）
  • 简单图论农场派对
  • 基于CentOS系统利用Kamailio搭建企业级SIP服务器
  • 青少年编程等级一级 自动打包机问题