一墩蔓、前言
本文詣在幫助像博主這樣沒有基礎(chǔ)的同學(xué)更好地理解二叉搜索樹中前驅(qū)節(jié)點(diǎn)的求法攘烛，以及為什么這么求就可以舶赔，高手童鞋就忽略吧...這其中可能有我個人理解不準(zhǔn)確的地方湃交，還請幫忙指正熟空。本文所總結(jié)的證明方法都是我自己歸納的所以不一定正確，給需要的同學(xué)作參考搞莺。
接下來就是正文內(nèi)容了
二息罗、前驅(qū)節(jié)點(diǎn)的定義
1. 定義：某個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指所有值小于該節(jié)點(diǎn)的節(jié)點(diǎn)中值最大的節(jié)點(diǎn)
舉例來說：途中的樹中，9的前驅(qū)是8,8的前驅(qū)是7,7的前驅(qū)是6,2的前驅(qū)是1,1沒有前驅(qū)腮敌。阱当。俏扩。
2. 如何求某個節(jié)點(diǎn)的前驅(qū)呢？
- 若一個節(jié)點(diǎn)有左子樹录淡，那么該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是其左子樹中值最大的節(jié)點(diǎn)
- 若一個節(jié)點(diǎn)沒有左子樹捌木，且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的右邊孩子，那么該節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即為其父節(jié)點(diǎn)嫉戚。
- 若一個節(jié)點(diǎn)沒有左子樹刨裆，且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左邊孩子澈圈，那么需要沿著其父親節(jié)點(diǎn)一直向樹的頂端尋找，直到找到一個節(jié)點(diǎn)P帆啃，P節(jié)點(diǎn)是其父節(jié)點(diǎn)Q的右邊孩子（可參考例子2的前驅(qū)結(jié)點(diǎn)是1）瞬女，那么Q就是該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
3. java實(shí)現(xiàn)
/*
* 找結(jié)點(diǎn)(x)的前驅(qū)結(jié)點(diǎn)。即努潘，查找"二叉樹中數(shù)據(jù)值小于該結(jié)點(diǎn)"的"最大結(jié)點(diǎn)"诽偷。
*/
public BSTNode<T> predecessor(BSTNode<T> x) {
// 如果x存在左孩子，則"x的前驅(qū)結(jié)點(diǎn)"為 "以其左孩子為根的子樹的最大結(jié)點(diǎn)"疯坤。
if (x.left != null)
return maximum(x.left);
// 如果x沒有左孩子报慕。則x有以下兩種可能：
// (01) x是"一個右孩子"，則"x的前驅(qū)結(jié)點(diǎn)"為 "它的父結(jié)點(diǎn)"压怠。
// (02) x是"一個左孩子"眠冈，則查找"x的最低的父結(jié)點(diǎn)，并且該父結(jié)點(diǎn)要具有右孩子"菌瘫，找到的這個"最低的父結(jié)點(diǎn)"就是"x的前驅(qū)結(jié)點(diǎn)"蜗顽。
BSTNode<T> y = x.parent;
while ((y!=null) && (x==y.left)) {//滿足條件，不斷往上追溯雨让，直到找到右祖先結(jié)點(diǎn)
x = y;
y = y.parent;
}
return y;
}
4. 用到的結(jié)論
接下來我們就要證明以上三個結(jié)論的正確性诫舅，在證明這三個結(jié)論正確的過程中需要用到另外三個結(jié)論：
結(jié)論一：在同一棵樹中，若存在關(guān)系a<b<c那么任意a和c的共同路徑都是b的路徑宫患。
結(jié)論二：在同一棵樹中刊懈，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假設(shè)共同路徑不為空，且b與任意a娃闲、c共同祖先都不相等）虚汛。
結(jié)論三：假設(shè)y是x的前驅(qū)節(jié)點(diǎn)，要么x是y的祖先皇帮，要么y是x的祖先
這三個結(jié)論是我針對二叉搜索樹的性質(zhì)總結(jié)出來的卷哩，并不標(biāo)準(zhǔn)，后面我會給出我的證明方法属拾，現(xiàn)在我們還是先拿來用将谊。
三、前驅(qū)節(jié)點(diǎn)求法的論證
接下來我們就要用這三個結(jié)論來證明三種情況下節(jié)點(diǎn)的前驅(qū)的求法了：
- 如果節(jié)點(diǎn)的左子樹不為空那么節(jié)點(diǎn)一定是左子樹的最大節(jié)點(diǎn)：
證明：證明這一點(diǎn)我們只需要證明在節(jié)點(diǎn)x存在左子樹的情況下節(jié)點(diǎn)x的前驅(qū)一定在x的左子樹中即可渐白。
首先我們假設(shè)節(jié)點(diǎn)x尊浓，左子樹最大節(jié)點(diǎn)為y，假設(shè)在樹的某一處存在一個節(jié)點(diǎn)z纯衍，滿足y<z<x（z必然不在x的左子樹中）栋齿。我們只需要證明z不存在即可。
根據(jù)結(jié)論一可以知道從根節(jié)點(diǎn)到節(jié)點(diǎn)x都是x和y的共同路徑，所以x也是z的路徑上的祖先瓦堵，同時z<x所以z位于 x的左子樹中基协，這和y是x左子樹中最大節(jié)點(diǎn)矛盾，故樹中不存在一個值z滿足y<z<x菇用。所以如果節(jié)點(diǎn)的左子樹不為空那么節(jié)點(diǎn)一定是左子樹的最大節(jié)點(diǎn)成立澜驮。
- 若一個節(jié)點(diǎn)沒有左子樹，且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的右邊孩子惋鸥，那么該節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即為其父節(jié)點(diǎn)：
證明：同樣我們假設(shè)節(jié)點(diǎn)x的父節(jié)點(diǎn)為y泉唁，x為y的右孩子所以y<x,假設(shè)在樹中存在一個值z滿足，y<z<x揩慕，那么由結(jié)論結(jié)論一可知從根節(jié)點(diǎn)到節(jié)點(diǎn)y都是x和y的共同路徑亭畜，那么y亦是節(jié)點(diǎn)z的路徑上的祖先之一，且z>y迎卤，所以z位于y的右子樹上此時y的右孩子是x拴鸵，所以z必然位于x的左子樹上，這與x沒有左子樹矛盾蜗搔，所以不存在z使y<z<x劲藐，y即是比節(jié)點(diǎn)x小的最大節(jié)點(diǎn)。所以若一個節(jié)點(diǎn)沒有左子樹樟凄，且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的右邊孩子聘芜，那么該節(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)即為其父節(jié)點(diǎn)。
- 若一個節(jié)點(diǎn)沒有左子樹缝龄， 且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左邊孩子汰现，那么需要沿著其父親節(jié)點(diǎn)一直向樹的頂端尋找，直到找到一個節(jié)點(diǎn)P叔壤，P節(jié)點(diǎn)是其父節(jié)點(diǎn)Q的右邊孩子（可參考例子2的前驅(qū)結(jié)點(diǎn)是1）瞎饲，那么Q就是該節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)（也可能不存在）。
證明： 該結(jié)論等價于：當(dāng)節(jié)點(diǎn)x的前驅(qū)節(jié)點(diǎn)存在時炼绘，x的前驅(qū)是離x最近的x的祖先中右節(jié)點(diǎn)為x祖先的節(jié)點(diǎn)嗅战。接下來我們證明x前驅(qū)存在時的情況。
由結(jié)論三可知俺亮，假設(shè)z是x的前驅(qū)驮捍，那么要么z是x的祖先，要么x是z的祖先脚曾，因?yàn)閦<x且x沒有左子樹东且，所以x的子樹中不存在比x小的值般妙，可見此時z是x的祖先，且由于x大于z所以x位于z的右子樹中
假設(shè)y是離x最近的x祖先中右節(jié)點(diǎn)為x的祖先的節(jié)點(diǎn)膛檀，
(1) 假設(shè)z是x的前驅(qū)驾孔，且z在y的上層丘薛，那么存在關(guān)系z<x,y<x蚓聘。由于z是x的前驅(qū)故z<y<x關(guān)系不成立缅糟，所以有y<z<x成立魔吐，由結(jié)論一可知y和x的任意公共路徑均是z的路徑堵漱，然而z位于y的上層综慎，所以該結(jié)論不成立。
(2) 假設(shè)z是x的前驅(qū)勤庐，且z在y的下層和x的上層之間示惊，且由于z是x的前驅(qū)故z<y<x關(guān)系不成立，所以y<z<x愉镰，所以z位于y的右子樹內(nèi)米罚，x位于y的右子樹內(nèi)，這與y是離x最近的右節(jié)點(diǎn)為x祖先的節(jié)點(diǎn)假設(shè)相悖丈探，故結(jié)論不成立录择。
綜上，x的前驅(qū)節(jié)點(diǎn)只能是y碗降。
四隘竭、證明結(jié)論二：在同一棵樹中，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假設(shè)共同路徑不為空讼渊，且b與任意a动看、c共同祖先不相等）。
證明：
現(xiàn)假設(shè)一顆存在a<b<c的樹爪幻，假設(shè)a和c的祖先分別為[ac(0),ac(1),ac(2),...,ac(n),ap(n+1),ap(n+2),...],[ac(0),ac(1),ac(2),...,ac(n),cp(n+1),cp(n+2),...]
此時a和c共同祖先集合為[ac(0),ac(1),ac(2),...,ac(n)]
現(xiàn)在我們假設(shè)我們要將與b相等的d插入樹中菱皆，那么，d必然會插到b的位置挨稿，即b與d等價搔预。
所以我們只要證明d插入后的路徑經(jīng)過a、c的共同祖先即可叶组。
- 當(dāng)共同祖先數(shù)量等于1時拯田，ac(0)為根節(jié)點(diǎn)，所以往ac(0)中插入d時ac(0)一定是d的祖先甩十。
- 我共同祖先數(shù)量大于1時：
我們采用數(shù)學(xué)歸納法來證明共同祖先數(shù)量大于1時d插入一定會經(jīng)過a船庇、c的共同祖先
定義插入位置p，
(1) p = 0時侣监，插入的節(jié)點(diǎn)為ac0(根節(jié)點(diǎn))鸭轮，插入后ac0成為d的祖先，且由于（ac1 - ac0）* （d - ac0） > 0橄霉，所以d會繼續(xù)插入下個節(jié)點(diǎn)ac1窃爷，
(2) p > 0時，我們假設(shè)當(dāng)前插入的節(jié)點(diǎn)位置為n-2時，ac(n-2)
成為d的祖先且d要插入下個節(jié)點(diǎn)為ac(n-1)按厘，成立医吊。我們只需要證明d插入下個節(jié)點(diǎn)ac(n-1)時ac(n-1)將成為d的祖先且d將繼續(xù)插入ac(n)即可。
(3) 當(dāng)d插入ac(n-1)時逮京，由于(ac(n)-ac(n-1)) * (d - ac(n - 1)) > 0所以當(dāng)d插入到ac(n-1)時ac(n-1)將成為d的祖先卿堂，并且d將繼續(xù)插入ac(n).
由數(shù)學(xué)歸納法可知，任意a懒棉、c共同祖先都是d的祖先草描，即b的祖先。
綜合情況1和2可知策严，在同一棵樹中穗慕，若a<b<c 那么任意a和c的共同祖先都是b的祖先（假設(shè)共同路徑不為空，且b與任意a妻导、c共同祖先不相等）
五逛绵、證明結(jié)論一：在同一棵樹中，若存在關(guān)系a<b<c那么任意a和c的共同路徑都是b的路徑栗竖。
證明：
- 由結(jié)論二可知當(dāng)節(jié)點(diǎn)b等于任何a和c的公共祖先時暑脆，a和c的共同祖先也是b的共同祖先，即a和c的共同路徑也是b的路徑狐肢。
- 當(dāng)b等于某一個是a和c的共同祖先時添吗，可以證明，b只能是最其下層的公共祖先份名。
我們可以用反證法來證明：假設(shè)b可以是a碟联、c的非最下層公共祖先，那么由于a<b<c可知a和c分別位于b的左右子樹上僵腺，也就不會再有任何共同的下層（低于b）公共祖先了鲤孵，所以假設(shè)不成立，因此b只可能是a和c的最下層公共祖先辰如。當(dāng)b是a普监、c的最下層公共祖先時任意a、c的公共路徑都是b的路徑顯然是成立的琉兜。
綜合1,2可知結(jié)論“在同一棵樹中凯正，若存在關(guān)系a<b<c那么任意a和c的共同路徑都是b的路徑⊥泱”成立
六廊散、證明結(jié)論三：假設(shè)y是x的前驅(qū)節(jié)點(diǎn)，要么x是y的祖先梧疲，要么y是x的祖先
證明：
反證法：假設(shè)x允睹，y均不是對方的祖先运准，由于x，y在同一棵樹上缭受，那么必然存在一個節(jié)點(diǎn)z使x和y分別位于y和x的左右子樹上胁澳，這樣也就存在關(guān)系y<z<x，那么y就不再是x的前驅(qū)節(jié)點(diǎn)贯涎，矛盾听哭。所以當(dāng)y是x的前驅(qū)節(jié)點(diǎn)時要么x是y的祖先要么y是x的祖先慢洋。
