BST和RBtree

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

创新互联公司成立10余年来，这条路我们正越走越好，积累了技术与客户资源，形成了良好的口碑。为客户提供成都网站制作、做网站、网站策划、网页设计、域名注册、网络营销、VI设计、网站改版、漏洞修补等服务。网站是否美观、功能强大、用户体验好、性价比高、打开快等等，这些对于网站建设都非常重要，创新互联公司通过对建站技术性的掌握、对创意设计的研究为客户提供一站式互联网解决方案，携手广大客户，共同发展进步。

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;