教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

二叉搜索树

介绍

二叉搜索树(Binary Search Tree,简称BST)是一种特殊的二叉树数据结构,它具有以下特点:对于树中的每个节点,其左子树中所有节点的值都小于该节点的值,右子树中所有节点的值都大于该节点的值。

核心特性

  1. 有序性:左子树上所有节点的值都小于根节点的值,右子树上所有节点的值都大于根节点的值
  2. 唯一性:树中不存在值相同的节点(标准实现中)
  3. 平均时间复杂度:查找、插入和删除操作的平均时间复杂度为O(log n),n是节点数量
  4. 最坏时间复杂度:如果树不平衡(比如形成链表),最坏情况下时间复杂度为O(n)
  5. 递归定义:每个子树也是一个二叉搜索树

基本操作

查找操作

  1. 从根节点开始
  2. 如果目标值等于当前节点值,则找到目标
  3. 如果目标值小于当前节点值,则在左子树中继续查找
  4. 如果目标值大于当前节点值,则在右子树中继续查找
  5. 如果到达叶节点仍未找到,则目标不存在

插入操作

...

目录