image.png 最佳用例是检索某数值,将目标节点值 num与节点值 cur.val比较,若没找到,执行 cur = cur.right或执行 cur = cur.left,继续搜索。 image.png 也可以插入:

image.png 删除: image.png image.png image.png image.png 这个后继结点一定是已有数据中最靠近(且略大于)待删除节点的。 image.png image.png 排序: image.png

二叉搜索树常见应用

  • 用作系统中的多级索引,实现高效的查找、插入、删除操作。
  • 作为某些搜索算法的底层数据结构。
  • 用于存储数据流,以保持其有序状态。

改良定义方式后:AVL 树

为了确保在持续添加和删除节点后,好看的二叉树不会退化成难用的普通二叉树,从而使得各种操作的时间复杂度保持在 级别,提出 AVL tree