鏈表中的哨兵是怎麼一個作用？

01-07

演算法導論中第十章鏈表有關哨兵那塊有些疑問，希望大神能指導一下我這個小白。1.哨兵的作用是什麼，書上的意思是使代碼簡介，降低常數因子。2.在實際中帶哨兵的雙向鏈表常見嗎，能不能舉幾個例子？3.能不能將哨兵放入到其他的數據結構中，網上查了可以用到紅黑樹中，但具體是怎麼樣操作的呢？

可以看看我這篇文章

哨兵元素的應用總結
哨兵，顧名思義，是用來解決國家之間邊界問題的，不直接參与生產活動。
同樣，計算機科學中提到的哨兵，也用來解決邊界問題。

在許多演算法中，存在「鄰居依賴問題」（我自己造的詞），在處理當前元素時，要涉及到它旁邊那個元素。那如果當前元素是邊界元素呢，它沒有旁邊那個元素，如果不作處理，程序就可能出錯；如果對它特別對待，就會增加代碼複雜性，還會降低程序效率。應用哨兵，也就是申請若干個多餘的元素作為邊界元素的鄰居，可以完美得解決這個問題。
下面，我們會舉一些哨兵應用的例子。
鏈表
單鏈表在插入和刪除時，需要修改前驅結點的後繼指針，這就形成了「鄰居依賴」，鏈表中第一個元素沒有前驅結點，如果沒有特殊處理，在插入和刪除第一個結點時，就會出錯。
所以我們可以申請一個頭結點，作為原本的第一個結點的前驅結點，問題也就解決了。但是在這種方式中，我們要插入或者刪除一個結點時，要知道它的前驅結點地址，這往往是麻煩的。
另一個方式，也是我更喜歡的方式，是申請一個尾結點，作為原本最後一個結點的後繼結點。
要刪除某個元素時，我們不刪除當前這個結點，而是用後繼結點的數據覆蓋當前結點的數據，再刪除後繼結點。這種方式，不需要訪問前驅結點，也就解決了獲取前驅結點的困難。插入元素也是同理。而最後一個結點沒有後繼結點，所以需要一個尾結點作為哨兵。
如果用的是雙鏈表，就需要在頭尾各加一個哨兵。
其它
在插入排序和歸併排序中，使用一個值為無窮大或者負無窮大的哨兵元素，能降低代碼複雜性，提高程序運行效率。

在二叉樹中，插入刪除元素時也會表現出「鄰居依賴」，也可以通過哨兵解決。
在n*m的矩形區域中，例如掃雷，一個點擊方塊時，要掃描周圍8個方塊的雷數，而邊界方塊的周圍不足8個方塊，一種解決方法就是在有效矩形區域的周圍，添加一圈的方塊，
但這個方法申請的哨兵數量有點多，數量是2n+2m-4,在實踐中應該酌情考慮。
可以使用哨兵的地方還有很多，只要存在「鄰居依賴」的地方，就可以考慮使用哨兵。

假設某個漆黑的夜晚，諸位在海岸的懸崖邊上玩一個遊戲。諸位站在距懸崖邊緣100米的地方，地上每隔1米就任意放1件物品。請找出這些物品中有沒有蘋果。

諸位每前進1米就要撿起地上的物品，檢查是否拿到了蘋果，同時還要檢查有沒有到達懸崖的邊緣（不檢查的話就有可能掉到海里），也就是說要對這兩種檢查反覆若干次。

使用了哨兵以後，就要先把起點挪到距懸崖邊緣101米的地方，再在懸崖的邊緣放置一個蘋果。這個蘋果就是哨兵，通過放置哨兵，諸位就一定能找到蘋果了。每前進1米只需檢查檢驗到的物品是不是蘋果就可以了。發現是蘋果以後，只需站在原地再檢查一步開外的情況。如果還沒有到達懸崖邊緣，就意味著找到了真正要找的蘋果。已經達到了懸崖邊緣，則說明現在手中的蘋果是哨兵，而沒有找到真正要找的蘋果。

哨兵這個說法說的太不大眾化了，說成援兵我都覺得比較好理解，說白了就是外援。

紅黑樹有一個性質是：葉結點的左右兩邊必須為黑色。

也就是本來葉結點如果沒有左右孩子直接初始化為NULL就是了，但它居然要黑色，意味著我需要新分配兩塊內存空間啥數據也不保存，tm就是為了給它塗上黑色然後掛到葉結點的left、right。當葉結點多起來的時候你說多浪費內存空間？理想的二叉樹結構是為了讓我們保存數據（key），而不是為了保存顏色吧？

所以哨兵這個外援就來了，我們申請一塊內存命名為哨兵，然後把這塊內存塗上黑色，之後所有沒有孩子的葉結點left、right都指向這個已塗上黑色的哨兵。

以上是紅黑樹哨兵的作用。

哨兵在每種情況下都是不同的，拿方程舉例：7x=14，讓兩邊同時除以7： $7/7*x=14/7$ ，方程就化簡成x=2了，那個7相當於你定義的哨兵，用來化簡方程，同理3x=15的哨兵是多少你應該知道了，用了那個哨兵就能化簡成x=5。數學題化簡就是用的哨兵來化簡，所以你可以回想下你曾經化簡數學題究竟用了多少哨兵。

還不理解我就拿演算法導論上的動態規劃里的鋼管切割問題來說吧。

q被設置成了負無限，其他if，for等你都知道翻譯成C語言是什麼樣子的，但是這個負無限怎麼翻譯？其實這個負無限就是一個哨兵，它的作用是我不關心它是什麼值，反正是負數就得了。

到這裡你就會發現，這次的哨兵只是一個值，而紅黑樹那個哨兵卻是一塊內存。所以哨兵是各種各樣的...所以回答你的第3個問題，不是能不能將哨兵放到其他的數據結構中，而是其他數據結構它們有自己的哨兵......

萌新正在自學演算法導論正好看見這個問題

A sentinel is a dummy object that allows us to simplify boundary conditions.

哨兵是用來簡化邊界問題的虛設對象

As shown in Figure 10.4, this change turns a regular doubly linked list into a circu-

lar, doubly linked list with a sentinel, in which the sentinel L:nil lies between the

head and tail. The attribute L:nil:next points to the head of the list, and L:nil:pre points to the tail. Similarly, both the next attribute of the tail and the pre at-

tribute of the head point to L: nil. Since L: nil: next points to the head, we can

eliminate the attribute L:head altogether, replacing references to it by references

to L:nil:next. Figure 10.4(a) shows that an empty list consists of just the sentinel,

and both L:nil:next and L:nil:pre point to L:nil.

哨兵優化雙向鏈表貌似就把雙向鏈表弄成了環形鏈表

3.rbt中的哨兵

reference:Introduction to Algorithms