WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数据结构部分简介
栈
队列
链表
哈希表
并查集
堆简介
二叉堆
配对堆
左偏树
分块思想
块状数组
块状链表
树分块
Sqrt Tree
单调栈
单调队列
ST 表
树状数组
线段树
李超线段树
区间最值操作 & 区间历史最值
划分树
二叉搜索树简介
Treap
Splay
WBLT
Size Balanced Tree
AVL 树
替罪羊树
笛卡尔树
左偏红黑树
跳表
可持久化数据结构简介
可持久化线段树
可持久化块状数组
可持久化平衡树
可持久化字典树
可持久化可并堆
线段树套线段树
平衡树套线段树
线段树套平衡树
树状数组套主席树
分块套树状数组
K-D Tree
珂朵莉树
Link Cut Tree
Euler Tour Tree
Top Tree
析合树
50 objects
本站非官方,所收集资源均来源于网络。
二叉搜索树简介 - 数据结构
## 二叉搜索树简介 二叉搜索树是一种二叉树的树形数据结构,其定义如下: 1. 空树是二叉搜索树。 2. 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。 3. 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。 4. 二叉搜索树的左右子树均为二叉搜索树。 二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。对于一个有 $n$ 个结点的二叉搜索树中,这些操作的最优时间复杂度为 $O(\log n)$ ,最坏为 $O(n)$ 。随机构造这样一棵二叉搜索树的期望高度为 $O(\log n)$ 。 ## 基本操作 在接下来的代码块中,我们约定 $n$ 为结点个数, $h$ 为高度, `val[x]` 为结点 $x$ 处存的数值, `cnt[x]` 为结点 $x$ 存的值所出现的次数, `lc[x]` 和 `rc[x]` 分别为结点 $x$ 的左子结点和右子结点。 ### 遍历二叉搜索树 由二叉搜索树的递归定义可得,二叉搜索树的中序遍历权值的序列为非降的序列。时间复杂度为 $O(n)$ 。 遍历一棵二叉搜索树的代码如下: ```cpp void print(int o) { // 遍历以 o 为根节点的二叉搜索树 if (!o) return; // 遇到空树,返回 print(lc[o]); // 递归遍历左子树 for (int i = 1; i <= cnt[o]; i++) printf("%d\n", val[o]); // 输出根节点信息 print(rc[o]); // 递归遍历右子树 } ``` ### 查找最小/最大值 由二叉搜索树的性质可得,二叉搜索树上的最小值为二叉搜索树左链的顶点,最大值为二叉搜索树右链的顶点。时间复杂度为 $O(h)$ 。 findmin 和 findmax 函数分别返回最小值和最大值所对应的结点编号 $o$ ,用 `val[o]` 可以获得相应的最小/最大值。 ```cpp int findmin(int o) { if (!lc[o]) return o; return findmin(lc[o]); // 一直向左儿子跳 } int findmax(int o) { if (!rc[o]) return o; return findmax(rc[o]); // 一直向右儿子跳 } ``` ### 插入一个元素 定义 `insert(o,v)` 为在以 $o$ 为根节点的二叉搜索树中插入一个值为 $v$ 的新节点。 分类讨论如下: 若 $o$ 为空,直接返回一个值为 $v$ 的新节点。 若 $o$ 的权值等于 $v$ ,该节点的附加域该值出现的次数自增 $1$ 。 若 $o$ 的权值大于 $v$ ,在 $o$ 的左子树中插入权值为 $v$ 的节点。 若 $o$ 的权值小于 $v$ ,在 $o$ 的右子树中插入权值为 $v$ 的节点。 时间复杂度为 $O(h)$ 。 ```cpp void insert(int& o, int v) { if (!o) { val[o = ++sum] = v; cnt[o] = siz[o] = 1; return; } siz[o]++; if (val[o] == v) { cnt[o]++; return; } if (val[o] > v) insert(lc[o], v); if (val[o] < v) insert(rc[o], v); } ``` ### 删除一个元素 定义 `del(o,v)` 为在以 $o$ 为根节点的二叉搜索树中删除一个值为 $v$ 的节点。 先在二叉搜索树中找到权值为 $v$ 的节点,分类讨论如下: 若该节点的附加 $\textit{cnt}$ 大于 $1$ ,只需要减少 $\textit{cnt}$ 。 若该节点的附加 $\textit{cnt}$ 为 $1$ : 若 $o$ 为叶子节点,直接删除该节点即可。 若 $o$ 为链节点,即只有一个儿子的节点,返回这个儿子。 若 $o$ 有两个非空子节点,一般是用它左子树的最大值或右子树的最小值代替它,然后将它删除。 时间复杂度 $O(h)$ 。 ```cpp int deletemin(int& o) { if (!lc[o]) { int u = o; o = rc[o]; return u; } else { int u = deletemin(lc[o]); siz[o] -= cnt[u]; return u; } } void del(int& o, int v) { // 注意 o 有可能会被修改 siz[o]--; if (val[o] == v) { if (cnt[o] > 1) { cnt[o]--; return; } if (lc[o] && rc[o]) o = deletemin(rc[o]); // 这里以找右子树的最小值为例 else o = lc[o] + rc[o]; return; } if (val[o] > v) del(lc[o], v); if (val[o] < v) del(rc[o], v); } ``` ### 求元素的排名 排名定义为将数组元素排序后第一个相同元素之前的数的个数加一。 维护每个根节点的子树大小 $\textit{siz}$ 。查找一个元素的排名,首先从根节点跳到这个元素,若向右跳,答案加上左儿子节点个数加当前节点重复的数个数,最后答案加上终点的左儿子子树大小加一。 时间复杂度 $O(h)$ 。 ```cpp int queryrnk(int o, int v) { if (val[o] == v) return siz[lc[o]] + 1; if (val[o] > v) return queryrnk(lc[o], v); if (val[o] < v) return queryrnk(rc[o], v) + siz[lc[o]] + cnt[o]; } ``` ### 查找排名为 k 的元素 在一棵子树中,根节点的排名取决于其左子树的大小。 若其左子树的大小大于等于 $k$ ,则该元素在左子树中; 若其左子树的大小在区间 $[k-\textit{cnt},k-1]$ ( $\textit{cnt}$ 为当前结点的值的出现次数)中,则该元素为子树的根节点; 若其左子树的大小小于 $k-\textit{cnt}$ ,则该元素在右子树中。 时间复杂度 $O(h)$ 。 ```cpp int querykth(int o, int k) { if (siz[lc[o]] >= k) return querykth(lc[o], k); if (siz[lc[o]] < k - cnt[o]) return querykth(rc[o], k - siz[lc[o]] - cnt[o]); return val[o]; // 如要找排名为 k 的元素所对应的结点,直接 return o 即可 } ```