本篇內(nèi)容介紹了“PHP代碼實現(xiàn)平衡二叉樹”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠?qū)W有所成！
創(chuàng)新互聯(lián)建站主營瑞昌網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,app軟件定制開發(fā),瑞昌h5微信平臺小程序開發(fā)搭建,瑞昌網(wǎng)站營銷推廣歡迎瑞昌等地區(qū)企業(yè)咨詢
平衡二叉樹（Self-Balancing Binary Search Tree 或者 Height-Balancing Binary Search Tree）譯為 自平衡的二叉查找樹或者高度平衡的二叉查找樹，簡稱平衡二叉樹，也叫 AVL 樹，是一種二叉排序樹。每個節(jié)點的左子樹和右子樹的高度差至多等于 1，我們將二叉樹上結(jié)點的左子樹深度減去右子樹深度的值稱為平衡因子 BF（Balance Factor），那么平衡二叉樹上所有結(jié)點的平衡因子只可能是 -1，0，1。只要樹上有結(jié)點的平衡因子的絕對值大于 1，則該二叉樹就是不平衡的。
下面舉四個例子：
圖1不滿足平衡二叉樹定義，58和88這兩個結(jié)點的平衡因子BF分別是2和-2，不是平衡二叉樹
圖2不是平衡二叉樹，因為平衡二叉樹首要要是二叉排序樹，59比58大卻是58的左子樹，這是不符合二叉排序樹的定義的
圖3不滿足平衡因子小于等于1的要求，對58這個節(jié)點來說，平衡因子BF的值是3，因而不是平衡二叉樹
圖4滿足平衡二叉樹的定義，是平衡二叉樹
平衡二叉樹構(gòu)建的基本思想就是在構(gòu)建二叉排序樹的過程中，每當插入一個結(jié)點時，先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹。在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應的旋轉(zhuǎn)（左旋或右旋），使之成為新的平衡子樹。
距離插入結(jié)點最近的，且平衡因子的絕對值大于1的結(jié)點為根的子樹，我們稱為最小不平衡子樹。
如下圖，當新插入結(jié)點37時，距離它最近的平衡因子絕對值超過1的結(jié)點是58 (即它的左子樹高度2減去右子樹高度0)，所以從58開始以下的子樹為最小不平衡子樹。
當右子樹比左子樹高，即平衡因子小于-1，需要進行左旋，如下圖
當右子樹比左子樹低，即平衡因子大于1，需要進行右旋，如下圖
假設(shè)插入節(jié)點的順序是{3,2,1,4,5,6,7,10,9,8}
根據(jù)二叉排序樹的特性，我們通常會將它構(gòu)建成如下圖1的樣子。雖然它完全符合二叉排序樹的定義，但是對這樣高度達到8的二叉樹查找是非常不利的。我們更期望能構(gòu)建成下圖2的樣子，這樣才能提供高效的查詢效率。
對于{3,2,1,4,5,6,7,10,9,8}的前兩位3和2，我們正常的構(gòu)建，到了第三個數(shù)1時發(fā)現(xiàn)根節(jié)點的平衡因子變成了2，需要把以 3 為根節(jié)點的子樹進行右旋
插入第四個節(jié)點 4 的時候，左右子樹高度為 -1，符合平衡二叉樹要求，繼續(xù)插入第五個節(jié)點，此時又不符合平衡二叉樹的要求了，這個時候右子樹比較高，需要左旋：旋轉(zhuǎn)的時候以最小不平衡子樹為單位，此時最小的不平衡子樹是3、4、5節(jié)點構(gòu)成的子樹，我們以4為中心進行左旋
繼續(xù)增加節(jié)點，當插入節(jié)點 6 時，發(fā)現(xiàn)根節(jié)點 2 上維護的高度差值為 -2，又不滿足平衡二叉樹了，這個時候，需要以 2 為中心對樹進行左旋：如下圖所示（右子樹中旋轉(zhuǎn)到根節(jié)點的節(jié)點對應子樹需要移到旋轉(zhuǎn)后二叉樹的左子樹中）
增加結(jié)點7，同樣的左旋，使得整棵樹達到平衡
繼續(xù)增加節(jié)點 10，結(jié)構(gòu)無變化。再插入節(jié)點 9，發(fā)現(xiàn)結(jié)點7的BF變成-2又需要調(diào)整。但是這次調(diào)整需要繞個彎，不能簡單的進行簡單的左旋，需要先將以10作為根節(jié)點的子樹做一次右轉(zhuǎn)，再將以7為根節(jié)點的子樹做一次左轉(zhuǎn)，讓這棵不平衡子樹轉(zhuǎn)化為平衡子樹
最后，插入節(jié)點8，此時情況和剛才類似，這個時候，我們以 9 為根節(jié)點對子樹進行右旋，再以6為根節(jié)點對子樹進行左旋，最終達到平衡狀態(tài)
相信大家應該有點明白，所謂的平衡二叉樹，其實就是在二叉排序樹創(chuàng)建過程中保證它的平衡性，一旦發(fā)現(xiàn)有不平衡的情況，馬上處理，這樣就不會造成不可收拾的情況出現(xiàn)。
通過剛才這個例子，你會發(fā)現(xiàn)，當最小不平衡子樹根結(jié)點的平衡因子BF是大于1時，就右旋，小于-1時就左旋
平衡二叉樹結(jié)點類
data = $data; } }
中序遍歷
重慶分公司
重慶分公司
left);
printf("%s\n", $tree->data);
midOrderTraverse($tree->right);
}平衡二叉樹
root;
}
public function insert(int $data) {
$this->insert_node($data, $this->root);
}
/**
* 插入節(jié)點
* @param int $data
* @param $tree
* @return bool 是否需要調(diào)整樹結(jié)構(gòu)，true：是，false：否
*/
protected function insert_node(int $data, &$tree) {
//創(chuàng)建節(jié)點
if (!$tree) {
$tree = new AVLNode($data);
$tree->bf = self::EH;
return true; //插入成功之后需要判斷是否需要調(diào)整
}
if ($data < $tree->data) {
//遞歸插入節(jié)點
if (!$this->insert_node($data, $tree->left)) {
return false;
} else {
//更正新插入節(jié)點對父節(jié)點的指向
if (empty($tree->left->parent)) {
$tree->left->parent = $tree;
}
//判斷是否需要調(diào)整子樹
switch ($tree->bf) {
case self::LH: //左子樹偏高，需要對左子樹進行調(diào)整
$this->left_balance($tree);
return false; //已經(jīng)進行過調(diào)整，不需要繼續(xù)調(diào)整
case self::EH:
$tree->bf = self::LH;
return true; //由等高變?yōu)樽蟾?，樹的整體高度發(fā)生變化，需要繼續(xù)判斷上層節(jié)點是否需要調(diào)整
case self::RH:
$tree->bf = self::EH;
return false; //由右高變?yōu)榈雀?，樹的整體高度沒有發(fā)生變化，不需要調(diào)整
}
}
} else {
if (!$this->insert_node($data,$tree->right)) {
return false;
} else {
if (empty($tree->right->parent)) {
$tree->right->parent = $tree;
}
switch ($tree->bf) {
case self::LH:
$tree->bf = self::EH;
return false;
case self::EH:
$tree->bf = self::RH;
return true;
case self::RH:
$this->right_balance($tree);
return false;
}
}
}
}
/**
* 右旋
* @param $tree
*/
protected function right_rotate(&$tree) {
//修改父節(jié)點與子樹之間的指向時需要特別注意根節(jié)點
$subTree = $tree->left;
//修改子樹對父節(jié)點的指向
if ($tree->parent) {
$subTree->parent = $tree->parent;
$left = false; //調(diào)整之前記錄當前調(diào)整的子樹是父節(jié)點的左子樹還是右子樹
if($tree->parent->left == $tree){
$left = true;
}
} else {
$subTree->parent = null; //根節(jié)點的父節(jié)點為空
}
//交換節(jié)點位置
$tree->left = $subTree->right;
$tree->parent = $subTree;
$subTree->right = $tree;
$tree = $subTree;
//修改父節(jié)點對子樹的指向
if (!$tree->parent) {
$this->root = $tree;
} else {
if ($left) {
$tree->parent->left = $tree;
} else {
$tree->parent->right = $tree;
}
}
}
/**
* 左旋
* @param $tree
*/
protected function left_rotate(&$tree) {
$subTree = $tree->right;
if ($tree->parent) {
$subTree->parent = $tree->parent;
$left = true;
if ($tree->parent->right == $tree) {
$left = false;
}
} else {
$subTree->parent = null;
}
$tree->right = $subTree->left;
$tree->parent = $subTree;
$subTree->left = $tree;
$tree = $subTree;
if (!$tree->parent) {
$this->root = $tree;
} else {
if ($left) {
$tree->parent->left = $tree;
} else {
$tree->parent->right = $tree;
}
}
}
/**
* 調(diào)整左子樹
* @param $tree
*/
protected function left_balance(&$tree) {
$subTree = $tree->left;
switch ($subTree->bf) {
case self::LH:
$tree->bf = $subTree->bf = self::EH; //先修改平衡因子，再進行旋轉(zhuǎn)
$this->right_rotate($tree);
break;
case self::RH:
$subTree_r = $subTree->right;
switch ($subTree_r->bf) {
case self::LH:
$tree->bf = self::RH;
$subTree->bf = self::EH;
break;
case self::RH:
$tree->bf = self::EH;
$subTree->bf = self::LH;
break;
}
$subTree_r->bf = self::EH;
$this->left_rotate($subTree);
$this->right_rotate($tree);
break;
}
}
/**
* 調(diào)整右子樹
* @param $tree
*/
protected function right_balance(&$tree) {
$subTree = $tree->right;
switch ($subTree->bf) {
case self::RH:
$tree->bf = $subTree->bf = self::EH;
$this->left_rotate($tree);
break;
case self::LH:
$subTree_l = $subTree->left;
switch ($subTree_l->bf) {
case self::RH:
$tree->bf = self::LH;
$subTree->bf = self::EH;
break;
case self::EH:
$tree->bf = $subTree->bf = self::EH;
break;
case self::LH:
$tree->bf = self::EH;
$subTree->bf = self::RH;
break;
}
$subTree_l->bf = self::EH;
$this->right_rotate($subTree);
$this->left_rotate($tree);
}
}
}
$avlTree = new AVLTree();
$avlTree->insert(3);
$avlTree->insert(2);
$avlTree->insert(1);
$avlTree->insert(4);
$avlTree->insert(5);
$avlTree->insert(6);
$avlTree->insert(7);
$avlTree->insert(10);
$avlTree->insert(9);
$avlTree->insert(8);
midOrderTraverse($avlTree->getTree());
print_r($avlTree->getTree());打印結(jié)果如下
E:\www\tree\2>php AVLTree.php 2 4 6 8 10 AVLNode Object ( [data] => 4 [left] => AVLNode Object ( [data] => 2 [left] => AVLNode Object ( [data] => 1 [left] => [right] => [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [right] => AVLNode Object ( [data] => 3 [left] => [right] => [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [right] => AVLNode Object ( [data] => 7 [left] => AVLNode Object ( [data] => 6 [left] => AVLNode Object ( [data] => 5 [left] => [right] => [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [right] => [bf] => 1 [parent] => AVLNode Object *RECURSION* ) [right] => AVLNode Object ( [data] => 9 [left] => AVLNode Object ( [data] => 8 [left] => [right] => [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [right] => AVLNode Object ( [data] => 10 [left] => [right] => [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [bf] => 0 [parent] => AVLNode Object *RECURSION* ) [bf] => -1 [parent] => )
“PHP代碼實現(xiàn)平衡二叉樹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！
