二叉平衡樹之删除節點操作
更好的判斷最小非平衡樹類型的方法
在前一篇文章中，我們知道最小非平衡樹可以分為四種類型，即：LL型、LR型、RR型和RL型。而且我也按照自己的了解，歸納了判斷是哪種類型的方法。總結一下就是：設最小非平衡樹的樹根為unbalance，首先看unbalance的左右子樹誰更高，如果左子樹更高則為LX型、如果是右子樹高則為RX型。再進一步，如果為LX型，将剛剛插入的節點的值value與unbalance左孩子進行比較，如果value大則為LR型，如果value小則為LL型。如果為RX型，将value與unbalance右孩子進行比較，如果value大則為RR型，如果value小則為RL型。
但是這種判斷類型的方法實際上存在不足之處，就是它是适用于插入節點導緻二叉樹失衡的情形，因為第二步中要用到剛剛插入的節點的值。如果是删除節點導緻的失衡就不能用這種方法判斷了，因為根本沒有value。
我在思考删除節點導緻失衡的情形時，發現我上面總結的判斷類型的方法實際上沒有總結到根源上。
其實我們調整樹的結構根本目的是為了降低左右子樹的高度差，也就是說調整的目的在于調整左右子樹的高度（當然在調整高度的同時要保證依然是一顆二叉查找樹）。實際上最小非平衡樹的四種類型，實際上就是對左右子樹高度的一個描述、一個分類：
比如LL型：
第一個L表示：unbalance的左子樹比右子樹高。第二個L表示unbalance的左孩子的左子樹比右子樹高。
LR型：
L表示：unbalance的左子樹比右子樹高。R表示unbalance的左孩子的右子樹比左子樹高。
RL型：
R表示：unbalance的右子樹比左子樹高。L表示unbalance的右孩子的左子樹比右子樹高。
RR型：
第一個R表示：unbalance的右子樹比左子樹高。第二個R表示unbalance的右孩子的右子樹比左子樹高。
是以總結一下就是，第一個字母（L或R）描述的是unbalance（也就是根節點）的左右子樹哪個更高，而第二個字母（L或R）描述的是unbalance的孩子（如果第一個是L則為左孩子，反之為右孩子）的左右子樹哪個更高。
這樣，添加節點和删除節點導緻的不平衡問題，對最小非平衡子樹的類型判斷就可以統一起來了！！！！！
另外需要指出，對于添加節點過程，并不存在，最小非平衡子樹的左右子樹等高的情況。比如下圖：
最小非平衡子樹的樹根為12，但是8節點的左右子樹高度相等，這才插入節點操作中是不可能産生的，因為剛剛插入的節點隻可能是7或10，但是無論哪個是剛剛插入的節點，在它插入之前就已經不平衡了。比如10是剛剛插入的節點，可以看到，在插入10之前，12就已經不平衡了。
但是這種情況卻可能在删除節點的過程中出現，比如下圖：
樹本來是平衡的，但是删除了14後，12就不平衡了，而這個時候8節點的左右子樹等高。這種情形也是LL型。是以對上面類型的分類，還需要加入unbalance的孩子的左右子樹等高的情況，添加之後就是：
LL型：
第一個L表示：unbalance的左子樹比右子樹高。第二個L表示unbalance的左孩子的左子樹比右子樹高，或者unbalance的左孩子的左右子樹等高。
第一個R表示：unbalance的右子樹比左子樹高。第二個R表示unbalance的右孩子的右子樹比左子樹高，或者unbalance的右孩子的左右子樹等高。
了解了上面，下面開始講删除節點操作
節點删除操作
對于二叉平衡樹的删除節點操作，可以分成兩步：
1、 删除節點，并且保證依然是一棵二叉排序樹
2、 對二叉平衡樹進行調整，保證是一棵平衡二叉樹
對于第二步，在将删除節點和插入節點導緻的非平衡問題中，最小非平衡子樹類型的判斷方法進行了統一後，實際上，對删除節點導緻失衡問題的調整和對于添加節點導緻的失衡問題的調整，方法也就統一了！
是以重點在第一步，即：删除節點，并且保證依然是一棵二叉排序樹。
當删除一個節點時，該節點的孩子們怎麼配置設定十分關鍵，（父親死之前要安排他的孩子，可憐天下父母心呀！）因為要保證依然是一棵二叉排序樹。
根據待删除節點的孩子的分布特點，可以将待删除節點分成三種類型，我們設待删除的節點為todelete：
1、 todelete沒有孩子，這種情況最簡單了，直接把它删了就好，因為它沒有孩子要配置設定。
2、 todelete隻有一個孩子，這種情況也比較簡單，用這個唯一的孩子将todelete取代了就好，所謂子承父業。
3、 todelete有兩個孩子，這種情況就比較複雜了。俗話說一碗水端不平，究竟将自己的皇位傳給哪個孩子呢？這可是個嚴肅的問題！中國古代講究宗法制，血統很重要，按照宗法制，皇位最合法的繼承者就是嫡長子！那在二叉排序樹中誰是todelete的嫡長子呢？答案是todelete的後繼節點，也就是比todelete大的節點中的最小的那一個！看到了吧，為什麼當初起名字的時候要叫它後繼節點呢。人家是要繼承皇位哒！
太子繼承了皇位，那太子的位置就空了，這個時候就需要有人來繼承太子的位置，那個人就是原太子的右孩子。好把，我們形式化一下，設todelete的後繼節點為y，y的右孩子為x（注意y是沒有左孩子的，因為如果存在左孩子那他的左孩子就是後繼節點，繼承皇位就沒他什麼事兒啦！）。這個時候，如果x為NULL那麼，将todelete用y的替換，然後釋放原來的y空間即可。如果x存在，那麼用y替換了todelete後，還要用x替換y，然後釋放原來x的空間，也就是太子成為皇帝，太子的兒子成為太子，然後太子的兒子的位置就空了，空了就清理了！
兩張圖，說明一下：
這裡要多說一句，對于單連結清單來說，如果用一個節點替換另一個節點，比如：用C替換B，我們可以先斷開AB之間的鍊，然後後将A連結到C，然後斷開BC之間的鍊，最後把B回收。當然我們也可以不斷開鍊，而是用C的内容替換B的内容，然後回收C。對于樹來說，也有這兩種方法，但是采用值替換的方法更簡單一下，原因嘛，是因為，單連結清單就一條鍊，而樹是會分叉的，會有多條鍊的！
當然還有一點需要注意，就是當後繼節點y是todelete的兒子的時候，和y是todelete的孫子（或者更後的位置）時，且x為NULL的時候，編寫代碼時會有一點出入。看代碼的時候就明白了（可能你用其他方法，可以避免這種差異，也說不定）
删除部分的代碼：
/**
* 删除指定的節點
* */
void delete_node(PBNode root,int value)
{
//找到該節點
PBNode node = get_node(root,value);
if(node == NULL)
return;
//找到副節點
PBNode p_node = get_father(root,value);
if(node->l_tree == NULL)
{
PBNode r = node->r_tree;
if(r == NULL)//為葉子節點的情況
{
//直接删除該節點即可
if(p_node != root)//反之，說明整個二叉樹就一個根節點
{
if(p_node->l_tree == node)
{
p_node->l_tree = NULL;
}
if(p_node->r_tree == node)
{
p_node->r_tree = NULL;
}
}
free_node(&node);
}
else//隻有右子樹的情況,采用值替換的方法比較科學
{
node->l_tree = r->l_tree;
node->r_tree = r->r_tree;
node->value = r->value;
free_node(&r);
}
}
else if(node->r_tree == NULL)//隻有左子樹的情況,采用值替換的方法比較科學
{
PBNode l = node->l_tree;
node->l_tree = l->l_tree;
node->r_tree = l->r_tree;
node->value = l->value;
free_node(&l);
}
else//既有左孩子又有右孩子,這種情況下我采用的是值交換的方式,這樣比較簡單，如果采用斷鍊再重新指向的方法代碼量就會加大
{
//找到後繼節點
PBNode y = node->r_tree;
PBNode y_p = y;//用于儲存後繼節點的父親節點
while(y->l_tree != NULL)
{
y_p = y;
y = y->l_tree;
}
PBNode x = y->r_tree; //後繼節點的右孩子
//替換後繼節點和待删除的節點
node->value = y->value;
if(x == NULL)//後繼節點沒有右孩子（根據後繼節點的定義可以知道，後繼節點一定沒有左孩子）
{
//後繼節點沒有右孩子的情況，在交換了後記節點和待删除節點的值後，直接删除後記節點即可
if(y_p == y)//後繼節點就是待删除節點的右孩子
{
node->r_tree = NULL;
}
else
{
y_p->l_tree = NULL;//後繼節點是待删除節點的右子樹的最左節點
}
free_node(&y);
}
else
{
//替換後繼節點的右孩子和後繼節點
y->l_tree = x->l_tree;
y->r_tree = x->r_tree;
y->value = x->value;
free_node(&x);
}
}
} 對于第二步，使二叉樹平衡，就再調用一下平衡的函數就好，我已經将删除節點和添加節點後引起的不平衡問題的處理方法進行了統一。
最後附上源檔案的連結和密碼（那個bst2.c是包含删除節點操作的，而且将調整的方法進行了統一）
連結：http://pan.baidu.com/s/1slyjF6t 密碼：k752
如果對你有用，請贊一個吧~~