更新時(shí)間:2022-09-27 10:12:05 來(lái)源:動(dòng)力節(jié)點(diǎn) 瀏覽1631次
完全二叉樹(shù)查找效率及深度是什么?動(dòng)力節(jié)點(diǎn)小編來(lái)告訴大家。二叉搜索樹(shù)也可稱為二叉查找樹(shù)(詳解二叉查找樹(shù)操作),我們?cè)跇?shù), 二叉樹(shù), 二叉搜索樹(shù)中提到,一個(gè)有n個(gè)節(jié)點(diǎn)的二叉樹(shù),它的最小深度為log(n),最大深度為n。比如下面兩個(gè)二叉樹(shù):

深度為n的二叉樹(shù)

這兩個(gè)二叉樹(shù)同時(shí)也是二叉搜索樹(shù)(參考樹(shù), 二叉樹(shù), 二叉搜索樹(shù))。注意,log以2為基底。log(n)是指深度的量級(jí)。根據(jù)我們對(duì)深度的定義,精確的最小深度為floor(log(n)+1)。
我們將處于同一深度的節(jié)點(diǎn)歸為一層。如果除最后一層外的其他層都被節(jié)點(diǎn)填滿時(shí),二叉樹(shù)有最小深度log(n)。
二叉搜索樹(shù)的深度越小,那么搜索所需要的運(yùn)算時(shí)間越小。一個(gè)深度為log(n)的二叉搜索樹(shù),搜索算法的時(shí)間復(fù)雜度也是log(n)。然而,我們?cè)诙嫠阉鳂?shù)中已經(jīng)實(shí)現(xiàn)的插入和刪除操作并不能讓保持log(n)的深度。如果我們按照8,7,6,5,4,3,2,1的順序插入節(jié)點(diǎn),那么就是一個(gè)深度為n的二叉樹(shù)。那么,搜索算法的時(shí)間復(fù)雜度為n。
n和log(n)的時(shí)間復(fù)雜度意味著什么呢?時(shí)間復(fù)雜度代表了完成算法所需要的運(yùn)算次數(shù)。時(shí)間復(fù)雜度越小,算法的速度越快。
可以看到,隨著元素的增加,log(n)的時(shí)間復(fù)雜度的增長(zhǎng)要遠(yuǎn)小于n。所以,我們自然希望二叉搜索樹(shù)能盡可能保持log(n)的深度。在上面深度為n的例子中,我們發(fā)現(xiàn),每個(gè)節(jié)點(diǎn)只有左節(jié)點(diǎn)被填滿。樹(shù)的每一層都有很多空位。能不能盡可能減少每一層的空位呢? (相應(yīng)的,減少樹(shù)的深度)
一種想法是先填滿一層,再去填充下一層,這樣就是一個(gè)完全二叉樹(shù)(complete binary tree)。這樣的二叉樹(shù)實(shí)現(xiàn)插入算法會(huì)比較復(fù)雜。
以上就是關(guān)于“完全二叉樹(shù)查找效率及深度”的介紹,大家如果對(duì)此比較感興趣,想了解更多相關(guān)知識(shí),不妨來(lái)關(guān)注一下動(dòng)力節(jié)點(diǎn)的Java在線學(xué)習(xí),里面的課程內(nèi)容從入門到精通,細(xì)致全面,適合沒(méi)有基礎(chǔ)的小伙伴學(xué)習(xí),希望對(duì)大家能夠有所幫助。
Java實(shí)驗(yàn)班
0基礎(chǔ) 0學(xué)費(fèi) 15天面授
Java就業(yè)班
有基礎(chǔ) 直達(dá)就業(yè)
Java夜校直播班
業(yè)余時(shí)間 高薪轉(zhuǎn)行
Java在職加薪班
工作1~3年,加薪神器
Java架構(gòu)師班
工作3~5年,晉升架構(gòu)
提交申請(qǐng)后,顧問(wèn)老師會(huì)電話與您溝通安排學(xué)習(xí)