BST和RBtree

发布时间:2020-06-17 17:09:02 作者:汇天下豪杰
来源:网络 阅读:991

讨论怎么用随机化的方法,使得二叉搜索树在大部分情况下都能保持平衡?

1、排序

  将数组构建为二叉搜索树,在进行中序遍历,就可顺序输出;

  BST的时间复杂度为:O(nlogn);最坏情况:O(n^2);

BST和RBtree


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条进行模型说明:

BST和RBtree

  RBtree的插入(红色结点):旋转算法,有些结点颜色可能的改变;

  插入时间复杂度:O(logn);旋转的时间复杂度为:O(1);

  RBtree的插入,插入结点之后,还的使树保持平衡;        

  插入算法的具体实现在前面博客中已经描述清楚。

  区间树的底层数据结构是RBtree;




推荐阅读:
  1. BST二叉搜索树
  2. 二叉搜索树—RBTree(红黑树)

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

rbtree bst bs

上一篇:java使用jar包时出现乱码的解决方法

下一篇:linux主要是由什么语言编写的

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》