树的相关概念

  • 父节点、子节点、兄弟节点

  • 没有父节点的节点叫根节点，没有子节点的节点叫叶节点

    SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

  • 节点的高度：节点到叶子节点的最长路径（边数）（从下往上，根节点高度为0）

  • 节点的深度：根节点到这个节点所经历的边数（从上往下，根节点的深度为0）

  • 节点的层数：节点的深度+1（类比楼房层数，地面是一楼）

  • 树的高度：根节点的高度

  • 示意图

10.二叉查找树 算法 第1张

二叉查找树

要求树中任意一个节点，其左子树每个结点的值都要小于这个节点的值，而右子树节点的值都大于这个节点的值

  • 查找：从根节点开始，如果它等于要找的值则返回；如果要查找值比根节点值小，则去左子树递归查找；如果要查找值比根节点值大，则去右子树递归查找
10.二叉查找树 算法 第2张
  • 插入：和查找相似，从根节点开始，递归找到合适的叶节点
10.二叉查找树 算法 第3张
  • 删除

    • 如果要删除的节点没有子节点，直接父节点对应指针置空

    • 如果仅有一个子结点，将父节点对应指针指向子节点

    • 如果有两个子节点，那么需要找到右子树的最小节点（或是左子树最大节点），用这个节点替换要删除的节点

10.二叉查找树 算法 第4张

支持重复数据的二叉查找树

  • 插入：如果碰到一个节点的值与要插入数据值相同，那么将其插入右子树，也就是把它当作大于这个节点的值处理

  • 查找：遇到相同节点值时并不直接结束，而是继续在右子树中查找，直到叶子节点才停止，将所有等于查找值的节点都找出来

  • 删除：找到相同节点值后，按一般的删除操作进行删除，然后继续在右子树中寻找是否有相同值节点，将所有等于删除值的节点全部删除

二叉查找树与哈希表相比的优势

  • 快速查找最大/小节点

  • 中序遍历可以输出有序的数据序列

  • 稳定动态扩容（哈希表有散列冲突，时间复杂度并不稳定）

  • 实现上要考虑的东西不多

  • （这样看来跳表还真是优秀啊）

二叉查找树的性能分析

  • 查找一个值时花费的时间其实和树的高度成正比

  • 最坏情况下，二叉树退化为链表，查找时间复杂度为O(n)

  • 最好情况，二叉平衡树，高度小于等于log2n，查找时间复杂度为O(logn)

  • 为了防止二叉树在插入数据后出现时间复杂度退化的情况，人们发明了平衡二叉树来解决这个问题

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄