二叉搜索树

二叉搜索树 #

一、基本操作 #

1、合法性 #

98. 验证二叉搜索树

  • 当前节点的值必须大于左子树所有的值(即左子树的最大值)
  • 借助辅助函数,传递信息/约束

2、遍历搜索 #

  • 二叉搜索树中的搜索

    • 类似二分搜索
  • 二叉搜索树中第K小的元素

    直观的:

    1. 中序遍历本身就是升序的;
    2. 所以中序遍历,记录当前遍历到第几个,和 k 比较。

    优化:

    1. 这样的话,每调用一次就要遍历一次,复杂度O(N)
    2. 想办法降到O(logN),二分的方法:如果当前节点排名 m, 和 k 去比较,不相等的就在左/右子树;
    3. 因此每个节点需要维护额外的信息:以自己为根的树有多少个节点。
  • 把二叉搜索树转换为累加树

    1. 倒着累加就行;
    2. 降序遍历时,先右子树,再左子树就可以。

#

二叉搜索树中的插入操作

  • 细节要注意。