完全二叉樹(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ù)

深度為log(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ù)的深度)

“緊致”的樹(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ì)大家能夠有所幫助。