溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

BST和RBtree

發(fā)布時(shí)間：2020-06-17 17:09:02 來(lái)源：網(wǎng)絡(luò) 閱讀：990 作者：匯天下豪杰 欄目：編程語(yǔ)言

討論怎么用隨機(jī)化的方法，使得二叉搜索樹在大部分情況下都能保持平衡？

1、排序

  將數(shù)組構(gòu)建為二叉搜索樹，在進(jìn)行中序遍歷，就可順序輸出；

  BST的時(shí)間復(fù)雜度為：O(nlogn)；最壞情況：O(n^2)；

BST和RBtree


BST與快速排序的算法思想極為相似；


2、隨機(jī)化BST

  (1)、隨機(jī)、均勻地打亂數(shù)組的序列；

  (2)、BST排序；

  隨機(jī)化BST樹，排序的算法時(shí)間復(fù)雜度：O(nlogn)；

  隨機(jī)化BST樹的高度為：O(logn)，所以查詢數(shù)字的時(shí)間復(fù)雜度為：O(logn)；


3、平衡搜索樹

  AVL樹

  2-3樹

  2-3-4樹

  B樹

  紅黑樹

  跳躍表

  樹堆


4、紅黑樹

  樹的高度為：O(logn)，其所有操作均在log(n)時(shí)間完成；

  滿足特征：

  i、每個(gè)結(jié)點(diǎn)不是紅的就是黑的，色域：一個(gè)位進(jìn)行表示；

  ii、根結(jié)點(diǎn)和葉子結(jié)點(diǎn)都是黑色；

  iii、每個(gè)紅色結(jié)點(diǎn)的父節(jié)點(diǎn)都是黑色；

  iiii、從該結(jié)點(diǎn)到達(dá)葉節(jié)點(diǎn)的所有路徑有相等的黑結(jié)點(diǎn)；(所有路徑的黑高度是一致的)。

對(duì)iiii條進(jìn)行模型說(shuō)明：

BST和RBtree

  RBtree的插入(紅色結(jié)點(diǎn))：旋轉(zhuǎn)算法，有些結(jié)點(diǎn)顏色可能的改變；

  插入時(shí)間復(fù)雜度：O(logn)；旋轉(zhuǎn)的時(shí)間復(fù)雜度為：O(1)；

  RBtree的插入，插入結(jié)點(diǎn)之后，還的使樹保持平衡；        

  插入算法的具體實(shí)現(xiàn)在前面博客中已經(jīng)描述清楚。

  區(qū)間樹的底層數(shù)據(jù)結(jié)構(gòu)是RBtree;




向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手