-
深入理解紅黑樹
大家都聽說過紅黑樹，也都知道紅黑樹很厲害，是計算機里面評價非常高的數(shù)據(jù)結(jié)構(gòu)。但是每當想學(xué)習紅黑樹的時候，卻總是找不到通俗易懂很好理解的學(xué)習資料。很多書上上來就是紅黑樹的定義，然后就是紅黑樹的實現(xiàn)，直接就把人給整暈了。光看紅黑樹的定義就有5條，為什么要有5條定義，為什么要這么定義，這么定義是什么意思，光定義都讓人懵了，更別說實現(xiàn)了。我看最近抖音上有很多人在講底層邏輯，只要你掌握了底層邏輯，其它的問題都不在話下，今天我們也來講一講紅黑樹的底層邏輯。在講之前我們先介紹一下紅黑樹的誕生，紅黑樹是Rudolf Bayer在1972年首先提出來的，不過當時并不叫紅黑樹，而是叫對稱二叉 B 樹(symmetric binary B-trees)。后來在1978年Leo J. Guibas 和 Robert Sedgewick 對此數(shù)據(jù)結(jié)構(gòu)進行了修改和完善，并重新命名為紅黑樹。為什么叫紅黑樹呢？有兩種說法，因為紅黑樹中要對節(jié)點連接做兩種顏色的區(qū)分，一說是因為當時的書寫筆只有紅色和黑色兩種顏色，另一說是當時的打印機只有紅和黑兩種顏色。
-
紅黑樹之個人見解
在第一部分我主要向大家闡述了自己對紅黑樹基本性質(zhì)的理解和紅黑樹插入結(jié)點算法的解釋，都是很表面，并沒有深入探究。我必須要承認的是，對于此，只是遵從于拿來主義，并不在其上做什么深入發(fā)展，所以，本著這個原則
-
linux內(nèi)存管理之紅黑樹算法源碼詳解
linux內(nèi)存管理模塊中使用紅黑樹算法來提升虛擬內(nèi)存查找速度，源碼請參考linux內(nèi)核目錄下rbtree.c文件。紅黑樹算法原理在閱讀紅黑樹算法源代碼之前最好先了解紅黑樹原理。rb_insert_co
-
什么是紅黑樹
《算法導(dǎo)論》上可不是這么說的：如果一個二叉查找樹滿足下面的紅黑性質(zhì)，那么則為一個紅黑樹。1）每個節(jié)點或是紅的，或者是黑的。2）每個葉子節(jié)點(NIL)是黑色的3）如果一個節(jié)點是紅色的，那么他的兩個兒子都
