二分搜索树

二分搜索树

概述

二分搜索树（Binary Search Tree，简称BST）是一种特殊的树结构，它是一种用于组织数据的结构，能够提供快速的查找、插入和删除操作。二分搜索树中的每个节点包含三个部分：键值、左子树和右子树。二分搜索树具有以下性质：

1. 每个节点的键值都大于其左子树中所有节点的键值。
2. 每个节点的键值都小于其右子树中所有节点的键值。
3. 左右子树也都是二分搜索树。

二分搜索树广泛应用于数据管理、算法实现、数据库索引等领域。

树结构

在二分搜索树中，每个节点通常包含以下信息：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };

查找

在二分搜索树中查找某个键值，我们可以从根节点开始，比较待查找键值与当前节点的键值：

1. 如果待查找键值小于当前节点的键值，则查找左子树。
2. 如果待查找键值大于当前节点的键值，则查找右子树。
3. 如果待查找键值等于当前节点的键值，则查找成功。

查找算法的时间复杂度为O(logn)，其中n为树中节点的个数。

插入

在二分搜索树中插入一个新节点，我们需要按照以下步骤进行：

1. 从根节点开始，比较待插入键值与当前节点的键值。
2. 如果待插入键值小于当前节点的键值，则将其插入到左子树；否则，插入到右子树。
3. 重复步骤1和2，直到找到一个空位。

插入操作的时间复杂度为O(logn)，在理想情况下（平衡的二分搜索树）可以达到O(1)。

删除

在二分搜索树中删除一个节