讨论怎么用随机化的方法，使得二叉搜索树在大部分情况下都能保持平衡？
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;
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
售后响应及时
7×24小时客服热线
数据备份
更安全、更高效、更稳定
价格公道精准
项目经理精准报价不弄虚作假
合作无风险
重合同讲信誉，无效全额退款
网站设计包含服务
网站制作流程
有效沟通方式
售后服务
+ 品牌创意
+ 宣传视频
+ 大陆官网
+ 外贸官网
+ 移动应用
+ 形象设计
网站建设
网站优化
网站制作
网站制作
网络营销
网站维护
公司简介
我们的观点
为什么选择我们
企业文化
支付方式
联系方式
在线留言
提交意向表
在线客服
来访路线
