歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
Linux教程網 >> Linux編程 >> Linux編程 >> AVL樹 VS 紅黑樹

AVL樹 VS 紅黑樹

日期:2017/3/1 9:46:02   编辑:Linux編程

平衡二叉樹的追求的是全局均衡,如在做插入,刪除操作時,需要調整整棵樹,顯然這是費時的,因此希望在做調整時,是局部調整,因此提出了紅黑樹,這樣一種高效的數據結構(也是最變態的一種數據結構)。

紅黑樹屬於非嚴格意義上的平衡二叉樹,說它不嚴格是因為它不是嚴格控制左、右子樹高度或節點數之差小於等於1。但紅黑樹高度依然是平均log(n),且最壞情況高度不會超過2log(n),這有數學證明。所以它算平衡樹,只是不嚴格。不過嚴格與否並不影響數據結構的復雜度。

“AVL trees are actually easier to implement than RB trees because there are fewer cases. And AVL trees require O(1) rotations on an insertion, whereas red-black trees require O(lg n).

In practice, the speed of AVL trees versus red-black trees will depend on the data that you're inserting. If your data is well distributed, so that an unbalanced binary tree would generally be acceptable (i.e. roughly in random order), but you want to handle bad cases anyway, then red-black trees will be faster because they do less unnecessary rebalancing of already acceptable data.On the other hand, if a pathological insertion order (e.g. increasing order of key) is common, then AVL trees will be faster, because the stricter balancing rule will reduce the tree's height.

Splay trees might be even faster than either RB or AVL trees,depending on your data access distribution. And if you can use a hash instead of a tree, then that'll be fastest of all. ”

32位Windows系統中,進程在用戶態可用的地址空間范圍是低2G(x64下是低8192G)。隨著進程不斷的申請和釋放內存,這個2G的地址空間,有的地址范圍是保留狀態(reserved),有的地址范圍是提交狀態(映射到了物理頁面,committed),有的地址范圍是空閒的。Windows采用平衡二叉樹把這些離散的地址范圍管理起來。

Linux內核進程調度使用紅黑樹進行管理。

常見的平衡二叉樹有紅黑樹和AVL樹兩種,其中紅黑樹應用更廣,C#/Java/C++STL等若干數據結構內部都是用紅黑樹實現的,然而Windows這次選擇了AVL樹。根據 《數據結構與算法分析:C語言描述(原書第2版) PDF+源代碼+習題答案 http://www.linuxidc.com/Linux/2014-04/99735.htm》,AVL樹的最大高度是1.44 * log(N+2) - 1.328,紅黑樹的最大高度是2.00* log(N+1)。與紅黑樹相比,AVL樹的插入刪除操作更慢一些,但是查詢操作更快。想必對進程地址空間的查詢操作更頻繁一些,所以AVL得以入選。

Copyright © Linux教程網 All Rights Reserved