二叉搜索树 #
一、基本操作 #
1、合法性 #
- 当前节点的值必须大于左子树所有的值(即左子树的最大值)
- 借助辅助函数,传递信息/约束
2、遍历搜索 #
- 类似二分搜索
直观的:
- 中序遍历本身就是升序的;
- 所以中序遍历,记录当前遍历到第几个,和
k
比较。
优化:
- 这样的话,每调用一次就要遍历一次,复杂度
O(N)
; - 想办法降到
O(logN)
,二分的方法:如果当前节点排名m
, 和k
去比较,不相等的就在左/右子树; - 因此每个节点需要维护额外的信息:以自己为根的树有多少个节点。
- 倒着累加就行;
- 降序遍历时,先右子树,再左子树就可以。
增 #
- 细节要注意。