网站备案收费吗,wordpress评论机器人,触屏网站模板,做个响应式网站多少钱平衡树——Treap 文章目录 平衡树——TreapBST定义性质操作插入insert(o, v)删除del(o, v)找前驱 / 后继get_prev(o)、get_next(o)查找最大 / 最小值get_min(o)、get_max(o)求元素排名get_rank(o)查找排名为 k k k的元素get_value_by_rank 平衡树左旋、右旋zag(o)、zig(o)左旋右…平衡树——Treap 文章目录 平衡树——TreapBST定义性质操作插入insert(o, v)删除del(o, v)找前驱 / 后继get_prev(o)、get_next(o)查找最大 / 最小值get_min(o)、get_max(o)求元素排名get_rank(o)查找排名为 k k k的元素get_value_by_rank 平衡树左旋、右旋zag(o)、zig(o)左旋右旋 BST
定义 空树是二叉搜索树。 若二叉搜索树的左子树不为空则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。
性质
二叉搜索树的中序遍历是一个有序序列
操作
插入insert(o, v) 若 o o o 为空直接返回一个值为 v v v 的新节点。 若 o o o 的权值等于 v v v该节点的附加域该值出现的次数自增 1 1 1。 若 o o o 的权值大于 v v v在 o o o 的左子树中插入权值为 v v v 的节点。 若 o o o 的权值小于 v v v在 o o o 的右子树中插入权值为 v v v 的节点。
删除del(o, v)
先在二叉搜索树中找到权值为 v 的节点分类讨论如下 若该节点的附加 cnt \textit{cnt} cnt 大于 1 1 1只需要减少 cnt \textit{cnt} cnt。 若该节点的附加 cnt \textit{cnt} cnt 为 1 1 1 若 o o o 为叶子节点直接删除该节点即可。 若 o o o 为链节点即只有一个儿子的节点返回这个儿子。 若 o o o 有两个非空子节点一般是用它左子树的最大值或右子树的最小值代替它然后将它删除。
找前驱 / 后继get_prev(o)、get_next(o) 前后驱表示中序遍历中前后一个位置以前驱为例 存在左子树则找到左子树中最右边的元素并返回。不存在左子树找第一个祖先节点中节点 o o o位于其右子树中返回这个祖先节点
查找最大 / 最小值get_min(o)、get_max(o)
由二叉搜索树的性质可得二叉搜索树上的最小值为二叉搜索树左链的顶点最大值为二叉搜索树右链的顶点。
求元素排名get_rank(o) 排名定义为将数组元素排序后第一个相同元素之前的数的个数加一 查找一个元素的排名首先从根节点跳到这个元素若向右跳答案加上左儿子节点个数加当前节点重复的数个数最后答案加上终点的左儿子子树大小加一。
查找排名为 k k k的元素get_value_by_rank
在一棵子树中根节点的排名取决于其左子树的大小。
若其左子树的大小大于等于 k k k则该元素在左子树中
若其左子树的大小在区间 [ k − cnt , k − 1 ] [k-\textit{cnt},k-1] [k−cnt,k−1] cnt \textit{cnt} cnt 为当前结点的值的出现次数中则该元素为子树的根节点
若其左子树的大小小于 k − cnt k-\textit{cnt} k−cnt则该元素在右子树中。
平衡树
对于一般的二叉搜索树有可能退化为链表。想象一棵每个结点只有右孩子的二叉搜索树那么它的性质就和链表一样插入与查找时间都是 O ( n ) O(n) O(n) 二叉搜索树的「平衡」概念是指每一个结点的左子树和右子树高度差最多为 1。
可以对不满足平衡条件的二叉搜索树进行调整使不平衡的二叉搜索树变得平衡。
调整要保证的标准还有二叉搜索树先天自带的条件二叉搜索树按照中序遍历得到从小到大的结点值序列。对于任意一个结点左子树各结点的最大值小于该结点的值该结点的值小于右子树各结点的最小值。只有保证这一点才能称为一个二叉搜索树。
左旋、右旋zag(o)、zig(o)
左旋
左旋左旋也称为「左单旋转」或「RR 平衡旋转」。对于结点 A A A 的左旋操作是指将 A A A 的右孩子 B B B 向左上旋转代替 A A A 成为根节点将 A A A 结点向左下旋转成为 B B B 的左子树的根结点 B B B 的原来的左子树变为 A A A 的右子树。
右旋
右旋右旋也称为「右单旋转」或「LL 平衡旋转」。对于结点 A A A 的右旋操作是指将 A A A 的左孩子 B B B 向右上旋转代替 A A A 成为根节点将 A A A 结点向右下旋转成为 B B B 的右子树的根结点 B B B 的原来的右子树变为 A A A 的左子树。
