紅黑樹(shù) 是一項(xiàng)重要的數(shù)據(jù)結(jié)構(gòu)
他提供快速的排序動(dòng)作， 支持二分查找
紅黑樹(shù)的定義
1 節(jié)點(diǎn)不是紅的就是黑的
2 根節(jié)點(diǎn)和葉子節(jié)點(diǎn)為黑的
3 紅色節(jié)點(diǎn)的父親節(jié)點(diǎn)是黑的
4 從根節(jié)點(diǎn)到葉子節(jié)點(diǎn) 走過(guò)的黑色節(jié)點(diǎn)的數(shù)目是相同的
紅黑樹(shù)是一種很復(fù)雜的數(shù)據(jù)結(jié)構(gòu) 最復(fù)雜的就是他的插入和刪除后的平衡問(wèn)題
在插入時(shí) 的算法
首先 插入的是紅色的節(jié)點(diǎn)
2 如果它的父親是黑色的 就做第八步
3 如果它的父親是紅色的而且它有叔叔節(jié)點(diǎn)也為紅色的 那么把他的父親和叔叔節(jié)點(diǎn)都設(shè)為黑色的 祖父節(jié)點(diǎn)設(shè)為紅色的 然后對(duì)爺爺 重新進(jìn)行第2步
4 如果他沒(méi)有樹(shù)樹(shù)節(jié)點(diǎn)或者叔叔節(jié)點(diǎn)為黑色 那么再看 如果他相對(duì)于父親的位置與父親相對(duì)于祖父的位置 如果一致 走到第6
5 如果不一致 那么對(duì)他于他的父親節(jié)點(diǎn)進(jìn)行輪轉(zhuǎn) 轉(zhuǎn)到一致 然后 再把指向它的指針指向他的父親節(jié)點(diǎn)
6 然后把現(xiàn)在指針指向的節(jié)點(diǎn)的父親（由于他已經(jīng)與父親換位了，父親是它）設(shè)為黑色， 爺爺設(shè)為紅色
7 然后再對(duì)爺爺重新進(jìn)行第二步
8 確保根節(jié)點(diǎn)為黑色的
其實(shí)如果想明白了也不是很復(fù)雜
可是現(xiàn)在看到刪除 我又覺(jué)得復(fù)雜了 呵呵
路走了還不到一半 還得努力