二叉搜索树 & 平衡树学习笔记

注意，这是一篇学习笔记。

二叉搜索树

定义

1. 空树是二叉搜索树
2. 若二叉搜索树的左子树非空，左子树内每个点的权值均 小于 二叉搜索树根节点的权值
3. 若二叉搜索树的右子树非空，右子树内每个点的权值均 大于 二叉搜索树根节点的权值
4. 二叉搜索树的左右子树为二叉搜索树

二叉搜索树中每个节点有一个权值 \(v\)，一个重复数量 \(cnt\)。还需要额外记录子树大小 \(siz\)。

性质

由定义可得一颗二叉搜索树的中序遍历的节点序列的权值单调递增。

操作

设树高为 \(h\)。

极值

由性质得最小值在二叉搜索树最小值在最左边的节点，最大值则在最右边的节点。

时间复杂度 \(O(h)\)。

搜索值

当在二叉搜索树中搜索 \(x\) 时，对于当前根节点 \(r\)，

• 若 \(r\) 为空，返回 false
• 若 \(r.v=x\)，返回 返回 true
• 若 \(x<r.v\)，在左子树中递归查找
• 若 \(r.v<x\)，在右子树中递归查找

时间复杂度 \(O(h)\)。