您好,登录后才能下订单哦!
讨论怎么用随机化的方法,使得二叉搜索树在大部分情况下都能保持平衡?
1、排序
将数组构建为二叉搜索树,在进行中序遍历,就可顺序输出;
BST的时间复杂度为:O(nlogn);最坏情况:O(n^2);
BST与快速排序的算法思想极为相似;
2、随机化BST
(1)、随机、均匀地打乱数组的序列;
(2)、BST排序;
随机化BST树,排序的算法时间复杂度:O(nlogn);
随机化BST树的高度为:O(logn),所以查询数字的时间复杂度为:O(logn);
3、平衡搜索树
AVL树
2-3树
2-3-4树
B树
红黑树
跳跃表
树堆
4、红黑树
树的高度为:O(logn),其所有操作均在log(n)时间完成;
满足特征:
i、每个结点不是红的就是黑的,色域:一个位进行表示;
ii、根结点和叶子结点都是黑色;
iii、每个红色结点的父节点都是黑色;
iiii、从该结点到达叶节点的所有路径有相等的黑结点;(所有路径的黑高度是一致的)。
对iiii条进行模型说明:
RBtree的插入(红色结点):旋转算法,有些结点颜色可能的改变;
插入时间复杂度:O(logn);旋转的时间复杂度为:O(1);
RBtree的插入,插入结点之后,还的使树保持平衡;
插入算法的具体实现在前面博客中已经描述清楚。
区间树的底层数据结构是RBtree;
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。