平衡二叉樹是什么？

平衡二叉樹是什么？平衡二叉樹是基于二分法的策略提高數(shù)據(jù)的查找速度的二叉樹的數(shù)據(jù)結(jié)構(gòu)。采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)，用這個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)減少無關(guān)數(shù)據(jù)的檢索，大大的提升了數(shù)據(jù)檢索的速度。

平衡二叉樹概念：

平衡二叉樹是基于二分法的策略提高數(shù)據(jù)的查找速度的二叉樹的數(shù)據(jù)結(jié)構(gòu)。

特點(diǎn)：

平衡二叉樹是采用二分法思維把數(shù)據(jù)按規(guī)則組裝成一個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)，用這個(gè)樹形結(jié)構(gòu)的數(shù)據(jù)減少無關(guān)數(shù)據(jù)的檢索，大大的提升了數(shù)據(jù)檢索的速度；平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)組裝過程有以下規(guī)則：

（1）非葉子節(jié)點(diǎn)只能允許最多兩個(gè)子節(jié)點(diǎn)存在。

（2）每一個(gè)非葉子節(jié)點(diǎn)數(shù)據(jù)分布規(guī)則為左邊的子節(jié)點(diǎn)小當(dāng)前節(jié)點(diǎn)的值，右邊的子節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)的值(這里值是基于自己的算法規(guī)則而定的，比如hash值)；

平衡樹的層級結(jié)構(gòu)：因?yàn)槠胶舛鏄洳樵冃阅芎蜆涞膶蛹墸╤高度）成反比，h值越小查詢越快、為了保證樹的結(jié)構(gòu)左右兩端數(shù)據(jù)大致平衡降低二叉樹的查詢難度一般會采用一種算法機(jī)制實(shí)現(xiàn)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)的平衡，實(shí)現(xiàn)了這種算法的有比如Treap、紅黑樹，使用平衡二叉樹能保證數(shù)據(jù)的左右兩邊的節(jié)點(diǎn)層級相差不會大于1.，通過這樣避免樹形結(jié)構(gòu)由于刪除增加變成線性鏈表影響查詢效率，保證數(shù)據(jù)平衡的情況下查找數(shù)據(jù)的速度近于二分法查找。