溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
討論怎么用隨機化的方法，使得二叉搜索樹在大部分情況下都能保持平衡？
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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
