首頁 > 常見問題 > 平衡二元樹的特徵有哪些?

平衡二元樹的特徵有哪些?

烟雨青岚
發布: 2020-06-29 10:18:01
原創
9694 人瀏覽過

平衡二元樹的特徵有:1、非葉子節點最多擁有兩個子節點;2、非葉子節值大於左邊子節點、小於右邊子節點;3、樹的左右兩邊的層級數相差不會大於1;4、沒有值相等重複的節點。

平衡二元樹的特徵有哪些?

平衡二元樹特徵:

(1)非葉子節點最多擁有兩個子節點;

(2)非葉子節值大於左邊子節點、小於右邊子節點;

(3)樹的左右兩邊的層級數相差不會大於1;

(4)沒有值相等重複的節點;

平衡二元樹概念

#平衡二元樹是基於二分法的策略提高資料的查找速度的二元樹的資料結構;

特點:

平衡二元樹是採用二分法思維把數據按規則組裝成一個樹形結構的數據,用這個樹形結構的數據減少無關數據的檢索,大大的提升了資料檢索的速度;平衡二元樹的資料結構組裝過程有以下規則:

(1)非葉子節點只能允許最多兩個子節點存在。

(2)每一個非葉子節點資料分佈規則為左邊的子節點小當前節點的值,右邊的子節點大於當前節點的值(這裡值是基於自己的演算法規則而定的,例如hash值);

平衡樹的層級結構:因為平衡二元樹查詢效能和樹的層級(h高度)成反比,h值越小查詢越快、為了保證樹的結構左右兩端數據大致平衡降低二元樹的查詢難度一般會採用一種演算法機制​​來實現節點資料結構的平衡,實現了這種演算法的有例如Treap、紅黑樹,使用平衡二元樹能保證資料的左右兩邊的節點層級相差不會大於1.,透過這樣避免樹形結構由於刪除增加變成線性鍊錶影響查詢效率,保證資料平衡的情況下查找資料的速度近於二分法查找;

更多相關知識,請訪問 PHP中文網! !

以上是平衡二元樹的特徵有哪些?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
來源:php.cn
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板