平衡二叉树平衡因子怎么计算_数据结构PHP 平衡二叉树(AVL)的平衡原理
生活随笔
收集整理的這篇文章主要介紹了
平衡二叉树平衡因子怎么计算_数据结构PHP 平衡二叉树(AVL)的平衡原理
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
這篇文章主要介紹一下?平衡二叉樹(AVL)，對于?二分搜索樹?來說，如果樹上的?元素?是順序?添加的，會導(dǎo)致數(shù)據(jù)退化成一個(gè)?鏈表，這樣就會造成很嚴(yán)重的性能問題，此時(shí)就需要在?二分搜索樹?的基礎(chǔ)上，保證元素插入時(shí)平衡，在了解?AVL?之前，需要您對?二分搜索樹?有一定的了解，可以參考之前的文章。
1.二分搜索樹的問題
如下圖所示，若向二分搜索樹中添加的元素是按照?順序?從小到大依次插入的，這樣會導(dǎo)致最后節(jié)點(diǎn)退化成鏈表:
Tips：反過來依次從大到插入元素也會出現(xiàn)退化成?鏈表。
2.二叉樹節(jié)點(diǎn)高度標(biāo)注示意圖
Tips：平衡因子等于左兒子高度減去右兒子高度，如45?和這個(gè)節(jié)點(diǎn)平衡因子?-2。
3.平衡二叉樹特點(diǎn)
對于任何一個(gè)節(jié)點(diǎn)，左兒子樹?和?右兒子樹?的高度差(Δh)的絕對值不能超過?1，高度差(Δh)?稱為?平衡因子。
本質(zhì)是帶了平衡功能的二分搜索樹。
平衡二叉樹(AVL) 的高度(h)和節(jié)點(diǎn)數(shù)之間的關(guān)系是?O(logn)級別的。
4.節(jié)點(diǎn)定義 PHP 代碼
對于?二分搜索樹?來說，AVL?需要在插入元素的時(shí)候保證?平衡，就需要引入節(jié)點(diǎn)高度(h)，所以節(jié)點(diǎn)定義需要在?二分搜索樹?節(jié)點(diǎn)定義的基礎(chǔ)上增加一個(gè)?height?屬性：
class AVLNode{public $e;
public $left = null;
public $right = null;
public $height = 1;
/**
* 構(gòu)造函數(shù) 初始化節(jié)點(diǎn)數(shù)據(jù)
* Node constructor.
* @param $e
*/
public function __construct($e){
$this->e = $e;
}
}
5.計(jì)算平衡因子
平衡因子等于左兒子高度減去右兒子高度，代碼如下：
/*** 獲取 AVL 節(jié)點(diǎn)的高度 h
* @param AVLNode $node
* @return int
*/
private function getHeight(AVLNode $node){
if ($node == null) {
return 0;
}
return $node->height;
}
/**
* 獲取節(jié)點(diǎn)平衡因子
* @param AVLNode $node
* @return int\
*/
private function getBalanceFactor(AVLNode $node){
if ($node == null){
return 0;
}
return $this->getHeight($node->left) - $this->getHeight($node->right);
}
6.更新節(jié)點(diǎn)高度
若遞歸插入元素時(shí)，需要更新節(jié)點(diǎn)高度，遞歸時(shí)當(dāng)前節(jié)點(diǎn)高度?h = 1 + (左右兒子中最大h)，代碼如下：
/*** 向 AVL 添加元素
* @param $e
*/
public function add($e){
$this->root = $this->recursionAdd($this->root, $e);
}
/**
* 遞歸向 AVL 添加元素
* @param Node $root
* @param $e
*/
private function recursionAdd($root, $e){
if ($root == null) { //若節(jié)點(diǎn)為空則添加元素 并且返回當(dāng)前節(jié)點(diǎn)信息
$root = new AVLNode($e);
$this->size++;
} elseif ($e < $root->e) { //若元素小于當(dāng)前節(jié)點(diǎn)元素 則向左節(jié)點(diǎn)遞歸添加元素
$root->left = $this->recursionAdd($root->left, $e);
} elseif ($e > $root->e) { //若元素大于當(dāng)前節(jié)點(diǎn)元素 則向右節(jié)點(diǎn)遞歸添加元素
$root->right = $this->recursionAdd($root->right, $e);
} //若元素等于當(dāng)前節(jié)點(diǎn)元素 則什么都不做
//更新節(jié)點(diǎn)高度
$root->height = 1 + ($this->getHeight($root->left) > $this->getHeight($root->right) ? $this->getHeight($root->left) : $this->getHeight($root->right));
return $root;
}
Tips：此處代碼直接貼出之前?二分搜索樹?代碼添加元素方法。
7.判斷二叉樹是否為二分搜索樹
若要判斷二叉樹是否為二分搜索樹，則需要將二叉樹中序遍歷，若輸出結(jié)果是按照順序依次從小到大排列的，則表示該?二叉樹?是一顆?二分搜索樹，采用遞歸思想層序遍歷然后將節(jié)點(diǎn)元素依次入隊(duì)，代碼如下，然后依次出隊(duì)查看出隊(duì)元素是否依次增大：
/*** 判斷二叉樹是否為二分搜索樹
*/
public function isBST(){
$queue = new QueueByLinkedList();
$this->inOrder($this->root, $queue);
do {
$e = $queue->dequeue();
if ($queue->getSize() > 0 && $e > $queue->getFront()) {
return false;
}
} while ($queue->getSize() > 0);
return true;
}
/**
* 中序遍歷二分搜索樹
*/
private function inOrder($root, $queue){
if ($root != null) {
$this->inOrder($root->left, $queue);
$queue->enqueue($root->e);
$this->inOrder($root->right, $queue);
}
}
8.判斷二叉樹是否為平衡二叉樹(AVL)
若需要判斷二叉樹是否為平衡二叉樹(AVL)，則需要遍歷二叉樹，判斷平衡因子?的絕對值是否大于?1，若大于?1?則不是?平衡二叉樹(AVL)，否則就是，代碼如下，使用遞歸處理：
/*** 判斷二叉樹是否為平衡二叉樹
* @return bool
*/
public function isBalanced(): bool{
return $this->recursionIsBalanced($this->root);
}
/**
* 遍歷二叉樹 判斷每個(gè)節(jié)點(diǎn)是否滿足平衡因子絕對值 小于等于 1
* @param $node
* @return bool
*/
private function recursionIsBalanced($node){
if ($node != null) {
if ($this->getBalanceFactor($node) < -1 || $this->getBalanceFactor($node) > 1) {
return false;
}
$left = $this->recursionIsBalanced($node->left);
$right = $this->recursionIsBalanced($node->right);
if (!$left || !$right) {
return false;
}
}
return true;
}
9.添加元素時(shí)的平衡原理
9.1 添加元素影響節(jié)點(diǎn)示意圖
若向?二叉樹?中添加元素，則只需判斷該節(jié)點(diǎn)的?父親節(jié)點(diǎn)?和?祖先節(jié)點(diǎn)?的?平衡因子?即可，如下圖所示：
9.2 添加元素在左兒子左側(cè)時(shí)右旋轉(zhuǎn)示意圖(LL)
Tips：如圖所示，新添加的元素是在左兒子的左側(cè)，此時(shí)?右旋轉(zhuǎn)可以糾正平衡。
9.3 添加元素在右兒子右側(cè)時(shí)左旋轉(zhuǎn)示意圖(RR)
Tips：如圖所示，新添加的元素是在右兒子的右側(cè)，此時(shí)?左旋轉(zhuǎn)可以糾正平衡。
9.4 添加元素在左兒子右側(cè)時(shí)先把左兒子左旋轉(zhuǎn)再右旋轉(zhuǎn)該節(jié)點(diǎn)(LR)
Tips：如圖所示，新添加的元素是在左兒子的右側(cè)，此時(shí)先把左兒子左旋轉(zhuǎn)，再?右旋轉(zhuǎn)該節(jié)點(diǎn)可以糾正平衡。
9.5 添加元素在右兒子左側(cè)時(shí)先把右兒子右旋轉(zhuǎn)再左旋轉(zhuǎn)該節(jié)點(diǎn)(RL)
Tips：如圖所示，新添加的元素是在右兒子的左側(cè)，此時(shí)先把右兒子右旋轉(zhuǎn)，再?左旋轉(zhuǎn)該節(jié)點(diǎn)可以糾正平衡。
9.3 右旋轉(zhuǎn)代碼
/** 對節(jié)點(diǎn) r 進(jìn)行右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后的節(jié)點(diǎn)* 35($r) 25($m)
* / \ / \
* 25($m) 45 15($n) 35($r)
* / \ 對35節(jié)點(diǎn)右旋轉(zhuǎn)之后 / \ / \
* 15($n) 30($a) 10 20 30($a) 45
* / \
* 10 20
* 對應(yīng)的關(guān)系如下：
* $m = $r->left;
* $a = $m->right;
* $m->right = $r;
* $r->left = $a;
*/
private function rightRotate($r)
{
$m = $r->left;
$a = $m->right;
$m->right = $r;
$r->left = $a;
//右旋轉(zhuǎn)之后只需要更新 $m 節(jié)點(diǎn)和 $r 節(jié)點(diǎn)的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);
return $m;
}
9.5 左旋轉(zhuǎn)代碼
/** 對節(jié)點(diǎn) r 進(jìn)行右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后的節(jié)點(diǎn)* 35($r) 25($m)
* / \ / \
* 25($m) 45 15($n) 35($r)
* / \ 對35節(jié)點(diǎn)右旋轉(zhuǎn)之后 / \ / \
* 15($n) 30($a) 10 20 30($a) 45
* / \
* 10 20
* 對應(yīng)的關(guān)系如下：
* $m = $r->left;
* $a = $m->right;
* $m->right = $r;
* $r->left = $a;
*/
private function rightRotate($r)
{
$m = $r->left;
$a = $m->right;
$m->right = $r;
$r->left = $a;
//右旋轉(zhuǎn)之后只需要更新 $m 節(jié)點(diǎn)和 $r 節(jié)點(diǎn)的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);
return $m;
}
9.6 完整PHP代碼
<?php require $root . '/QueueByLinkedList/QueueByLinkedList.php';class AVL{private $root;private $size;/*** 構(gòu)造函數(shù) 初始化 AVL
* BinarySearchTree constructor.
*/public function __construct(){$this->root = null;$this->size;
}/** 對節(jié)點(diǎn) r 進(jìn)行右旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后的節(jié)點(diǎn)
* 35($r) 25($m)
* / \ / \
* 25($m) 45 15($n) 35($r)
* / \ 對35節(jié)點(diǎn)右旋轉(zhuǎn)之后 / \ / \
* 15($n) 30($a) 10 20 30($a) 45
* / \
* 10 20
* 對應(yīng)的關(guān)系如下：
* $m = $r->left;
* $a = $m->right;
* $m->right = $r;
* $r->left = $a;
*/private function rightRotate($r){
$m = $r->left;
$a = $m->right;
$m->right = $r;
$r->left = $a;//右旋轉(zhuǎn)之后只需要更新 $m 節(jié)點(diǎn)和 $r 節(jié)點(diǎn)的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);return $m;
}/** 對節(jié)點(diǎn) r 進(jìn)行左旋轉(zhuǎn)操作，返回旋轉(zhuǎn)后的節(jié)點(diǎn)
* 35($r) 45($m)
* / \ / \
* 30 45($m) 35($n) 55($r)
* / \ 對35節(jié)點(diǎn)左旋轉(zhuǎn)之后 / \ / \
* 40($a) 55($n) 30 40 50($a) 60
* / \
* 50 60
* 對應(yīng)的關(guān)系如下：
* $m = $r->right;
* $a = $m->left;
* $m->left = $r;
* $r->right = $a;
*/private function leftRotate($r){
$m = $r->right;
$a = $m->left;
$m->left = $r;
$r->right = $a;//左旋轉(zhuǎn)之后只需要更新 $m 節(jié)點(diǎn)和 $r 節(jié)點(diǎn)的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);return $m;
}/**
* 判斷二叉樹是否為二分搜索樹
*/public function isBST(): bool{
$queue = new QueueByLinkedList();$this->inOrder($this->root, $queue);do {
$e = $queue->dequeue();if ($queue->getSize() > 0 && $e > $queue->getFront()) {return false;
}
} while ($queue->getSize() > 0);return true;
}/**
* 判斷二叉樹是否為平衡二叉樹
* @return bool
*/public function isBalanced(): bool{return $this->recursionIsBalanced($this->root);
}/**
* 遍歷二叉樹 判斷每個(gè)節(jié)點(diǎn)是否滿足平衡因子絕對值 小于等于 1
* @param $node
* @return bool
*/private function recursionIsBalanced($node){if ($node != null) {if ($this->getBalanceFactor($node) < -1 || $this->getBalanceFactor($node) > 1) {return false;
}
$left = $this->recursionIsBalanced($node->left);
$right = $this->recursionIsBalanced($node->right);if (!$left || !$right) {return false;
}
}return true;
}/**
* 中序遍歷二分搜索樹
*/private function inOrder($root, $queue){if ($root != null) {$this->inOrder($root->left, $queue);
$queue->enqueue($root->e);$this->inOrder($root->right, $queue);
}
}/**
* 獲取 AVL 節(jié)點(diǎn)的高度 h
* @param AVLNode $node
* @return int
*/private function getHeight($node){if ($node == null) {return 0;
}return $node->height;
}/**
* 獲取當(dāng)前搜索樹元素個(gè)數(shù)
* @return mixed
*/public function getSize(){return $this->size;
}/**
* 判斷當(dāng)前 AVL 是否為空
* @return bool
*/public function isEmpty(): bool{return $this->size == 0;
}/**
* 向 AVL 添加元素
* @param $e
*/public function add($e){$this->root = $this->recursionAdd($this->root, $e);
}/**
* 遞歸向 AVL 添加元素
* @param Node $root
* @param $e
*/private function recursionAdd($root, $e){if ($root == null) { //遞歸到底的情況，若節(jié)點(diǎn)為空則添加元素 并且返回當(dāng)前節(jié)點(diǎn)信息
$root = new AVLNode($e);$this->size++;
} elseif ($e < $root->e) { //若元素小于當(dāng)前節(jié)點(diǎn)元素 則向左節(jié)點(diǎn)遞歸添加元素
$root->left = $this->recursionAdd($root->left, $e);
} elseif ($e > $root->e) { //若元素大于當(dāng)前節(jié)點(diǎn)元素 則向右節(jié)點(diǎn)遞歸添加元素
$root->right = $this->recursionAdd($root->right, $e);
} //若元素等于當(dāng)前節(jié)點(diǎn)元素 則什么都不做//更新節(jié)點(diǎn)高度
$root->height = 1 + ($this->getHeight($root->left) > $this->getHeight($root->right) ? $this->getHeight($root->left) : $this->getHeight($root->right));//平衡的維護(hù)
$balanceFactor = $this->getBalanceFactor($root);//LL 添加元素在左兒子左側(cè)if ($balanceFactor > 1 && $this->getBalanceFactor($root->left) >= 0) {$this->rightRotate($root);
}//RR 添加元素在右兒子右側(cè)if ($balanceFactor < -1 && $this->getBalanceFactor($root->left) <= 0) {$this->leftRotate($root);
}//LR 添加元素在左兒子右側(cè)if ($balanceFactor > 1 && $this->getBalanceFactor($root->right) < 0) {//先把左兒子左旋轉(zhuǎn)
$root->left = $this->leftRotate($root->left);//再把該節(jié)點(diǎn)右旋轉(zhuǎn)
$root = $this->rightRotate($root);
}//RL 添加元素在右兒子左側(cè)if ($balanceFactor < -1 && $this->getBalanceFactor($root->right) < 0) {//先把右兒子右旋轉(zhuǎn)
$root->right = $this->leftRotate($root->right);//再把該節(jié)點(diǎn)左旋轉(zhuǎn)
$root = $this->leftRotate($root);
}return $root;
}/**
* 獲取節(jié)點(diǎn)平衡因子
* @param AVLNode $node
* @return int\
*/private function getBalanceFactor($node){if ($node == null) {return 0;
}return $this->getHeight($node->left) - $this->getHeight($node->right);
}/**
* 判斷 AVL 是否包含某個(gè)元素
* @param $e
* @return bool
*/public function contains($e): bool{return $this->recursionContains($this->root, $e);
}/**
* 遞歸判斷 AVL 是否包含某元素
* @param $root
* @param $e
* @return bool
*/private function recursionContains($root, $e): bool{if ($root == null) { //若當(dāng)前節(jié)點(diǎn)為空 則表示不存在元素 $ereturn false;
} elseif ($e == $root->e) { //若 $e 等于當(dāng)前節(jié)點(diǎn)元素，則表示樹包含元素 $ereturn true;
} elseif ($e < $root->e) { //若 $e 小于當(dāng)前節(jié)點(diǎn)元素，則去左兒子樹遞歸查詢是否包含節(jié)點(diǎn)return $this->recursionContains($root->left, $e);
} else { //若 $e 大于當(dāng)前節(jié)點(diǎn)元素，則去右兒子樹遞歸查詢是否包含節(jié)點(diǎn)return $this->recursionContains($root->right, $e);
}
}/**
* 前序遍歷
*/public function preTraversal(){$this->recursionPreTraversal($this->root, 0);
}/**
* 前序遍歷的遞歸
*/public function recursionPreTraversal($root, $sign_num){echo $this->getSign($sign_num);//打印深度if ($root == null) {echo "null
";return;
}echo $root->e . "
"; //打印當(dāng)前節(jié)點(diǎn)元素$this->recursionPreTraversal($root->left, $sign_num + 1);$this->recursionPreTraversal($root->right, $sign_num + 1);
}/**
* 中序遍歷
*/public function midTraversal(){$this->recursionMidTraversal($this->root, 0);
}/**
* 中序遍歷的遞歸
*/public function recursionMidTraversal($root, $sign_num){if ($root == null) {echo $this->getSign($sign_num);//打印深度echo "null
";return;
}$this->recursionMidTraversal($root->left, $sign_num + 1);echo $this->getSign($sign_num);//打印深度echo $root->e . "
";$this->recursionMidTraversal($root->right, $sign_num + 1);
}/**
* 后序遍歷
*/public function rearTraversal(){$this->recursionRearTraversal($this->root, 0);
}/**
* 后序遍歷的遞歸
*/public function recursionRearTraversal($root, $sign_num){if ($root == null) {echo $this->getSign($sign_num);//打印深度echo "null
";return;
}$this->recursionRearTraversal($root->left, $sign_num + 1);$this->recursionRearTraversal($root->right, $sign_num + 1);echo $this->getSign($sign_num);//打印深度echo $root->e . "
";
}/**
* 前序遍歷壓棧實(shí)現(xiàn)
*/public function preTraversalByStack(){
$stack = new StackByLinkedList();//將根節(jié)點(diǎn)壓入棧
$stack->push($this->root);while (!$stack->isEmpty()) {//出棧
$node = $stack->pop();if ($node != null) { //若出棧的當(dāng)前節(jié)點(diǎn)不是空echo $node->e . "
"; //先入棧//先入棧右兒子
$stack->push($node->right);//然后入棧左兒子
$stack->push($node->left);
} else { //若是空echo "null
";
}
}
}/**
* 中序遍歷壓棧實(shí)現(xiàn)
*/public function midTraversalByStack(){
$stack = new StackByLinkedList();//將根節(jié)點(diǎn)壓入棧
$stack->push($this->root);//循環(huán)依次出棧
$node = $stack->pop();do {if ($node != null) { //若出棧的當(dāng)前節(jié)點(diǎn)不是空//先入棧右兒子
$stack->push($node->right);echo $node->e . "
"; //然后打印當(dāng)前節(jié)點(diǎn)信息//最后入棧左兒子
$stack->push($node->left);
} else { //若是空echo "null
";
}//繼續(xù)出棧
$node = $stack->pop();
} while (!$stack->isEmpty());
}/**
* 層序遍歷實(shí)現(xiàn)
*/public function tierTraversalByLinkedList(){
$queue = new QueueByLinkedList();//將根節(jié)點(diǎn)入隊(duì)
$queue->enqueue($this->root);//循環(huán)依次出隊(duì)
$node = $queue->dequeue();do {if ($node != null) { //若出棧的當(dāng)前節(jié)點(diǎn)不是空echo $node->e . "
"; //然后打印當(dāng)前節(jié)點(diǎn)信息
$queue->enqueue($node->left);//左兒子入隊(duì)
$queue->enqueue($node->right);//右兒子入隊(duì)
} else { //若是空echo "null
";
}//繼續(xù)出隊(duì)
$node = $queue->dequeue();
} while (!$queue->isEmpty());
}/**
* 獲取最小元素
* @return mixed
*/public function getMin(){return $this->getMinNode($this->root)->e;
}/**
* 獲取某顆樹最小元素節(jié)點(diǎn)
* @param $root
* @return mixed
*/private function getMinNode($root){for ($node = $root; $node != null; $node = $node->left) {if ($node->left != null) {
$root = $node->left;
} else {
$root = $node;
}
}return $root;
}/**
* 獲取最大元素
* @return mixed
*/public function getMax(){return $this->getMaxNode($this->root)->e;
}/**
* 獲取某顆樹最大元素節(jié)點(diǎn)
* @param $root
* @return mixed
*/private function getMaxNode($root){for ($node = $root; $node != null; $node = $node->right) {if ($node->right != null) {
$root = $node->right;
} else {
$root = $node;
}
}return $root;
}/**
* 刪除 AVL 元素
* @param $e
*/public function remove($e){$this->root = $this->recursionRemove($this->root, $e);
}/**
* 遞歸刪除 AVL 元素
* @param $root
* @param $e
*/private function recursionRemove($root, $e){if ($root != null) {if ($e == $root->e) {
$root = $this->joinRemoveNode($root);
} elseif ($e < $root->e) {
$root->left = $this->recursionRemove($root->left, $e);
} else {
$root->right = $this->recursionRemove($root->right, $e);
}
}return $root;
}/**
* 拼接刪除節(jié)點(diǎn) 返回新節(jié)點(diǎn)
*/private function joinRemoveNode($root){if ($root->left != null && $root->right == null) {
$root = $root->left;
} elseif ($root->left == null && $root->right != null) {
$root = $root->right;
} else {
$leftMax = $this->getMaxNode($root->left);
$leftMax->right = $root->right;
$root = $root->left;
}return $root;
}public function getSign($num){
$str = "";for ($i = 0; $i < $num; $i++) {
$str .= "-----";
}return $str;
}
}class AVLNode{public $e;public $left = null;public $right = null;public $height = 1;/**
* 構(gòu)造函數(shù) 初始化節(jié)點(diǎn)數(shù)據(jù)
* Node constructor.
* @param $e
*/public function __construct($e){$this->e = $e;
}
}
10.輸出演示
<?php require 'AVL.php';$avl = new AVL();for ($i = 1; $i <= 3; $i++) { //按順序添加元素
$avl->add($i);
}
var_dump($avl->isBST());//判斷是否為二分搜索樹
var_dump($avl->isBalanced());//判斷是否平衡
演示如下：
代碼倉庫 ：https://gitee.com/love-for-poetry/data-structure
掃碼關(guān)注愛因詩賢
總結(jié)
以上是生活随笔為你收集整理的平衡二叉树平衡因子怎么计算_数据结构PHP 平衡二叉树(AVL)的平衡原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： python客户价值分析_航空公司客户价
- 下一篇： 前后端分离重复提交_阿里一面：如何保证A