二叉搜索树
介绍
二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树数据结构,它具有以下特点:对于树中的每个节点,其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。
核心特性
- 有序性:左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值
- 唯一性:树中不存在值相同的节点(标准实现中)
- 平均时间复杂度:查找、插入和删除操作的平均时间复杂度为O(log n),n是节点数量
- 最坏时间复杂度:如果树不平衡(比如形成链表),最坏情况下时间复杂度为O(n)
- 递归定义:每个子树也是一个二叉搜索树
基本操作
查找操作
- 从根节点开始
- 如果目标值等于当前节点值,则找到目标
- 如果目标值小于当前节点值,则在左子树中继续查找
- 如果目标值大于当前节点值,则在右子树中继续查找
- 如果到达叶节点仍未找到,则目标不存在
插入操作
...