完全二叉樹查找效率及深度是什么？動力節(jié)點小編來告訴大家。二叉搜索樹也可稱為二叉查找樹（詳解二叉查找樹操作），我們在樹, 二叉樹, 二叉搜索樹中提到，一個有n個節(jié)點的二叉樹，它的最小深度為log(n)，最大深度為n。比如下面兩個二叉樹:

深度為n的二叉樹

深度為log(n)的二叉樹

這兩個二叉樹同時也是二叉搜索樹(參考樹, 二叉樹, 二叉搜索樹)。注意，log以2為基底。log(n)是指深度的量級。根據(jù)我們對深度的定義，精確的最小深度為floor(log(n)+1)。

我們將處于同一深度的節(jié)點歸為一層。如果除最后一層外的其他層都被節(jié)點填滿時，二叉樹有最小深度log(n)。

二叉搜索樹的深度越小，那么搜索所需要的運算時間越小。一個深度為log(n)的二叉搜索樹，搜索算法的時間復(fù)雜度也是log(n)。然而，我們在二叉搜索樹中已經(jīng)實現(xiàn)的插入和刪除操作并不能讓保持log(n)的深度。如果我們按照8，7，6，5，4，3，2，1的順序插入節(jié)點，那么就是一個深度為n的二叉樹。那么，搜索算法的時間復(fù)雜度為n。

n和log(n)的時間復(fù)雜度意味著什么呢?時間復(fù)雜度代表了完成算法所需要的運算次數(shù)。時間復(fù)雜度越小，算法的速度越快。

可以看到，隨著元素的增加，log(n)的時間復(fù)雜度的增長要遠(yuǎn)小于n。所以，我們自然希望二叉搜索樹能盡可能保持log(n)的深度。在上面深度為n的例子中，我們發(fā)現(xiàn)，每個節(jié)點只有左節(jié)點被填滿。樹的每一層都有很多空位。能不能盡可能減少每一層的空位呢? (相應(yīng)的，減少樹的深度)

“緊致”的樹

一種想法是先填滿一層，再去填充下一層，這樣就是一個完全二叉樹(complete binary tree)。這樣的二叉樹實現(xiàn)插入算法會比較復(fù)雜。

以上就是關(guān)于“完全二叉樹查找效率及深度”的介紹，大家如果對此比較感興趣，想了解更多相關(guān)知識，不妨來關(guān)注一下動力節(jié)點的Java在線學(xué)習(xí)，里面的課程內(nèi)容從入門到精通，細(xì)致全面，適合沒有基礎(chǔ)的小伙伴學(xué)習(xí)，希望對大家能夠有所幫助。