平衡樹演算法題

A. 題目3． 平衡二叉樹演算法查找樹中某節點的時間復雜度是多少

平均查找的時間復雜度為O(log n)。

平衡樹的查找過程和排序樹的相同。在查找過程中和給定值進行比較關鍵字個數不超過樹的深度。

如果二叉樹的元素個數為n，那麼不管是對樹進行插入節點、查找、刪除節點都是log(n)次循環調用就可以了。它的時間復雜度相對於其他數據結構如數組等是最優的。

是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。常用演算法有紅黑樹、AVL、Treap、伸展樹等。

(1)平衡樹演算法題擴展閱讀：

二叉樹也是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹演算法有五種基本形態：

(1)空二叉樹——(a)

(2)只有一個根結點的二叉樹——(b);

(3)右子樹為空的二叉樹——(c);

(4)左子樹為空的二叉樹——(d);

(5)完全二叉樹——(e)

注意：盡管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。