数据结构与算法3- 二叉搜索树

小书匠  数据结构与算法  算法工程师 

1. 二叉搜索树的定义：

  • 二叉搜索树是一颗二叉树，可以为空。满足以下性质：
    • 非空左子树的所有键值小于其根节点的键值
    • 非空右子树的所有键值大于其根节点的键值

2. 二叉搜索树的基本操作：

  • 查找最小值：在树的最左分支的端节点上
  • 查找最大值：在树的最右分支的端节点上
  • 查找：
    • S1. 如果搜索树为空，返回false
    • S2. 如果树非空，根节点键值与X比较：
      • S2.1 键值小于X，则转向右子树
      • S2.2 键值大于X，则转向左子树
      • S2.3 两者相等，搜索完成，返回true
    • 特征：查找的路径是一条从根到某一叶节点的路径
  • 插入节点：
    • 在树中查找待插入的元素值
      • 如果存在，则放弃操作
      • 如果不存在，则查找终止的位置就是X应该插入的位置
  • 删除节点：需要考虑3中情况
    • CASE1. 删除叶节点：直接删除，然后修改其父节点中指向子节点的指针为null
    • CASE2. 删除只有一个子节点的节点：将该节点的父节点的指针指向子节点
    • CASE3. 删除有左右子节点的节点：首要目标是保持二叉树的有序性
      • Solution1. 选取右子树中的最小元素替代
      • Solution2. 选取左子树中的最大元素替代
      • 上述两种元素均最多只有一个子节点（否则最大/小不成立）
      • 然后再在节点的右/左子树中删除交换后的节点（回归到CASE1/2)
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄