【软考】数据结构 - 树结构 - 二叉搜索树（Binary Search Tree，BST）

爱被打了一巴掌 2024-03-24 15:07 77阅读 0赞

## 一、BST二叉搜索树是什么？ ##

BST（Binary Search Tree）是一种二叉搜索树  
BST二叉搜索树是一种有序的、树形数据结构

## 二、BST二叉搜索树的性质 ##

BST二叉搜索树具有以下性质：

*  每个节点有0个或2个子节点（最多有两个子节点）。
 *  对于每个节点，
    
     *  其左子树的所有节点的值都小于该节点的值（左子节点的值小于父节点的值）
     *  而右子树的所有节点的值都大于该节点的值（右子节点的值大于父节点的值）。

## 三、BST二叉搜索树的时间复杂度 ##

BST二叉搜索树这种结构/特质，使得在树中查找某个元素具有很好的性能

*  在BST中，平均时间复杂度为 O(log n)。
 *  在BST中，查找、插入和删除的时间复杂度均为O(log n)，其中n为树中节点的数量。

## 四、BST二叉搜索树的应用 ##

BST二叉搜索树用于高效地查找、插入和删除数据。

BST二叉搜索树可以用来实现很多数据结构和算法，例如：

### 4.1 有序集合 ###

将元素插入到 BST 中时按照其值排序，  
可以实现有序集合的常见操作，如查找、插入、删除等。

### 4.2 二叉搜索树 ###

BST 是一种二叉搜索树，  
因此可以用来实现二叉搜索树的常见操作，如查找、插入、删除等。

### 4.3 哈希表 ###

将 BST 的每个节点作为哈希表的一个元素，  
可以实现快速查找和插入操作。

### 4.4 最小堆 ###

将 BST 的每个节点的值与其子节点的值比较，将最小值放在根节点上，  
可以实现最小堆的常见操作，如查找、插入、删除等。

## 五、BST的构建过程 ##

BST的构建过程如下：

根节点为要查找的第一个值。  
如果当前节点的值等于要查找的值，返回该节点。  
如果要查找的值小于当前节点的值，则在左子树中继续查找。  
如果要查找的值大于当前节点的值，则在右子树中继续查找。  
如果当前节点为叶子节点且要查找的值不在树中，则返回空节点或特殊标记表示未找到。

## 六、BST的插入过程 ##

BST的插入过程如下：

从根节点开始遍历BST，找到要插入的位置。  
如果当前节点的值等于要插入的值，直接返回该节点。  
如果要插入的值小于当前节点的值，则在左子树中继续查找。  
如果要插入的值大于当前节点的值，则在右子树中继续查找。  
找到一个空位置，将新节点插入到该位置上，并更新父节点的指针。

## 七、BST的删除过程 ##

BST的删除过程如下：

从根节点开始遍历BST，找到要删除的节点。  
如果要删除的节点没有子节点，直接将其从树中删除。  
如果要删除的节点只有一个子节点，将其子节点连接到其父节点上。  
如果要删除的节点有两个子节点，找到该节点的前驱节点（即左子树中的最大值）或后继节点（即右子树中的最小值），用其代替要删除的节点的位置，并将其子节点连接到前驱节点或后继节点上。

发表评论取消回复

表情：

评论列表（有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读

相关【软考】数据结构 - 树结构 - 平衡二叉搜索树（红黑树）

一、红黑树是什么？红黑树（Red-Black Tree）是一种具有自平衡特性的二叉搜索树。二、红黑树的特性 2.1 红黑树的颜色属性红黑树得名于它的特

红太狼/ 2024年03月26日 20:00/ 0 赞/ 74 阅读

相关【软考】数据结构 - 树结构 - B树和B+树

一、B树（B-Tree）介绍 1.1 B树（B-Tree）是什么？ B树（B-Tree）是一种常用的、高效的、自平衡的树形数据结构 B树（B-Tree）是一种

系统管理员/ 2024年03月24日 15:07/ 0 赞/ 76 阅读

相关【软考】数据结构 - 树结构 - 平衡二叉搜索树（AVL树）

一、AVL树是什么？ AVL树是一种具有自平衡特性的二叉搜索树 AVL树的名字来源于它的发明者们：G. M. Adelson-Velsky和E. M. Landis。

心已赠人/ 2024年03月24日 15:07/ 0 赞/ 20 阅读

相关【软考】数据结构 - 树结构 - 二叉搜索树（Binary Search Tree，BST）

一、BST二叉搜索树是什么？ BST（Binary Search Tree）是一种二叉搜索树 BST二叉搜索树是一种有序的、树形数据结构二、BST二叉搜索树的性

爱被打了一巴掌/ 2024年03月24日 15:07/ 0 赞/ 78 阅读

相关 Validate Binary Search Tree（C++验证二叉搜索树）

（1）注意边界 / Definition for a binary tree node. struct TreeNode {

淩亂°似流年/ 2022年10月12日 15:53/ 0 赞/ 163 阅读

相关数据结构-二叉树(binary tree)-二叉查找树(binary search tree)

\二叉树(binary) 二叉树就是节点的度不大于2的树，即树中每个节点的子节点最多只有两个。每个节点的子节点分为左子节点和右子节点，并且左右子节点的顺序不能改变。 ![

朱雀/ 2022年08月22日 01:24/ 0 赞/ 32 阅读

相关【软考】-数据结构-平衡二叉树

【平衡二叉树的由来】：平衡二叉树是一个排序二叉树，用来查找。有这样一个规律：同样一个二叉排序树。像下图这样： ![201509241547

傷城~/ 2022年08月08日 18:00/ 0 赞/ 204 阅读

相关二叉搜索树（binary search tree）

定义二叉搜索树：二叉树中任何节点的键值一定大于其左子树中每一个节点的键值，并且小于其右子树中每一个节点的键值。查找基于此，在二叉搜索树中搜索最小元素和最大元

电玩女神/ 2022年08月08日 14:39/ 0 赞/ 170 阅读

相关【树结构】二叉搜索树

二叉搜索树二叉搜索树定义二叉搜索树BST的优点以及缺点二叉搜索树的Java实现 1.结点的数据结构的定义 2. 计算二叉

以你之姓@/ 2022年07月13日 11:26/ 0 赞/ 192 阅读

相关数据结构——树结构【二叉树与二分搜索树】

关于树的一些概念节点的度 > 结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称

╰+哭是因爲堅強的太久メ/ 2022年05月09日 05:08/ 0 赞/ 254 阅读