思路:
紅黑樹欲刪除節(jié)點(d)有兩個子節(jié)點的情況下恤煞,想直接刪除節(jié)點不好處理施籍,
轉(zhuǎn)換成只有一個子節(jié)點或沒有子節(jié)點的情況居扒,則更好處理
一般是找后繼節(jié)點(s),然后交換欲刪除節(jié)點(d)和后繼節(jié)點(s)
后繼節(jié)點可以簡單理解為比當前節(jié)點大的節(jié)點中最小的節(jié)點
交換的方式可以有兩種:
1.值交換
2.節(jié)點位置交換
位置交換時丑慎,應(yīng)注意后繼節(jié)點的位置不同的兩種情況
1.欲刪除節(jié)點(d)和后繼節(jié)點(s)不直接相鄰
2.欲刪除節(jié)點(d)和后繼節(jié)點(s)相鄰,即s是d的右子節(jié)點
寫代碼時竿裂,應(yīng)注意區(qū)分這兩種情況