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