数据结构-PHP 平衡二叉树(AVL)的平衡原理
码农天地 -
这篇文章主要介绍一下 平衡二叉树(AVL)，对于 二分搜索树 来说，如果树上的 元素 是顺序 添加的，会导致数据退化成一个 链表，这样就会造成很严重的性能问题，此时就需要在 二分搜索树 的基础上，保证元素插入时平衡，在了解 AVL 之前，需要您对 二分搜索树 有一定的了解，可以参考之前的文章。
如下图所示，若向二分搜索树中添加的元素是按照 顺序 从小到大依次插入的，这样会导致最后节点退化成链表:
链表。2.二叉树节点高度标注示意图Tips：平衡因子等于左儿子高度减去右儿子高度，如45 和这个节点平衡因子 -2。3.平衡二叉树特点对于任何一个节点，左儿子树 和 右儿子树 的高度差(Δh)的绝对值不能超过 1，高度差(Δh) 称为 平衡因子。本质是带了平衡功能的二分搜索树。平衡二叉树(AVL) 的高度(h)和节点数之间的关系是 O(logn)级别的。4.节点定义 PHP 代码对于 二分搜索树 来说，AVL 需要在插入元素的时候保证 平衡，就需要引入节点高度(h)，所以节点定义需要在 二分搜索树 节点定义的基础上增加一个 height 属性：
class AVLNode
{
public $e;
public $left = null;
public $right = null;
public $height = 1;
/**
* 构造函数 初始化节点数据
* Node constructor.
* @param $e
*/
public function __construct($e) {
$this->e = $e;
}
}平衡因子等于左儿子高度减去右儿子高度，代码如下：
/**
* 获取 AVL 节点的高度 h
* @param AVLNode $node
* @return int
*/
private function getHeight(AVLNode $node) {
if ($node == null) {
return 0;
}
return $node->height;
}
/**
* 获取节点平衡因子
* @param AVLNode $node
* @return int
*/
private function getBalanceFactor(AVLNode $node){
if ($node == null){
return 0;
}
return $this->getHeight($node->left) - $this->getHeight($node->right);
}若递归插入元素时，需要更新节点高度，递归时当前节点高度 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) { //若节点为空则添加元素 并且返回当前节点信息
$root = new AVLNode($e);
$this->size++;
} elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素
$root->left = $this->recursionAdd($root->left, $e);
} elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素
$root->right = $this->recursionAdd($root->right, $e);
} //若元素等于当前节点元素 则什么都不做
//更新节点高度
$root->height = 1 + ($this->getHeight($root->left) > $this->getHeight($root->right) ? $this->getHeight($root->left) : $this->getHeight($root->right));
return $root;
}二分搜索树 代码添加元素方法。7.判断二叉树是否为二分搜索树若要判断二叉树是否为二分搜索树，则需要将二叉树中序遍历，若输出结果是按照顺序依次从小到大排列的，则表示该 二叉树 是一颗 二分搜索树，采用递归思想层序遍历然后将节点元素依次入队，代码如下，然后依次出队查看出队元素是否依次增大：
/**
* 判断二叉树是否为二分搜索树
*/
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);
}
}若需要判断二叉树是否为平衡二叉树(AVL)，则需要遍历二叉树，判断平衡因子 的绝对值是否大于 1，若大于 1 则不是 平衡二叉树(AVL)，否则就是，代码如下，使用递归处理：
/**
* 判断二叉树是否为平衡二叉树
* @return bool
*/
public function isBalanced(): bool {
return $this->recursionIsBalanced($this->root);
}
/**
* 遍历二叉树 判断每个节点是否满足平衡因子绝对值 小于等于 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.3 添加元素在右儿子右侧时左旋转示意图(RR)Tips：如图所示，新添加的元素是在右儿子的右侧，此时 左旋转可以纠正平衡。9.4 添加元素在左儿子右侧时先把左儿子左旋转再右旋转该节点（LR）Tips：如图所示，新添加的元素是在左儿子的右侧，此时先把左儿子左旋转，再 右旋转该节点可以纠正平衡。9.5 添加元素在右儿子左侧时先把右儿子右旋转再左旋转该节点（RL）Tips：如图所示，新添加的元素是在右儿子的左侧，此时先把右儿子右旋转，再 左旋转该节点可以纠正平衡。9.3 右旋转代码 /** 对节点 r 进行右旋转操作，返回旋转后的节点
* 35($r) 25($m)
* / /
* 25($m) 45 15($n) 35($r)
* / 对35节点右旋转之后 / /
* 15($n) 30($a) 10 20 30($a) 45
* /
* 10 20
* 对应的关系如下：
* $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;
//右旋转之后只需要更新 $m 节点和 $r 节点的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);
return $m;
} /** 对节点 r 进行右旋转操作，返回旋转后的节点
* 35($r) 25($m)
* / /
* 25($m) 45 15($n) 35($r)
* / 对35节点右旋转之后 / /
* 15($n) 30($a) 10 20 30($a) 45
* /
* 10 20
* 对应的关系如下：
* $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;
//右旋转之后只需要更新 $m 节点和 $r 节点的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);
return $m;
}<?php
require $root . '/QueueByLinkedList/QueueByLinkedList.php';
class AVL
{
private $root;
private $size;
/**
* 构造函数 初始化 AVL
* BinarySearchTree constructor.
*/
public function __construct() {
$this->root = null;
$this->size;
}
/** 对节点 r 进行右旋转操作，返回旋转后的节点
* 35($r) 25($m)
* / /
* 25($m) 45 15($n) 35($r)
* / 对35节点右旋转之后 / /
* 15($n) 30($a) 10 20 30($a) 45
* /
* 10 20
* 对应的关系如下：
* $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;
//右旋转之后只需要更新 $m 节点和 $r 节点的高度
$r->height = $this->getHeight($r);
$m->height = $this->getHeight($m);
return $m;
}
/** 对节点 r 进行左旋转操作，返回旋转后的节点
* 35($r) 45($m)
* / /
* 30 45($m) 35($n) 55($r)
* / 对35节点左旋转之后 / /
* 40($a) 55($n) 30 40 50($a) 60
* /
* 50 60
* 对应的关系如下：
* $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;
//左旋转之后只需要更新 $m 节点和 $r 节点的高度
$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);
}
/**
* 遍历二叉树 判断每个节点是否满足平衡因子绝对值 小于等于 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 节点的高度 h
* @param AVLNode $node
* @return int
*/
private function getHeight($node) {
if ($node == null) {
return 0;
}
return $node->height;
}
/**
* 获取当前搜索树元素个数
* @return mixed
*/
public function getSize() {
return $this->size;
}
/**
* 判断当前 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) { //递归到底的情况，若节点为空则添加元素 并且返回当前节点信息
$root = new AVLNode($e);
$this->size++;
} elseif ($e < $root->e) { //若元素小于当前节点元素 则向左节点递归添加元素
$root->left = $this->recursionAdd($root->left, $e);
} elseif ($e > $root->e) { //若元素大于当前节点元素 则向右节点递归添加元素
$root->right = $this->recursionAdd($root->right, $e);
} //若元素等于当前节点元素 则什么都不做
//更新节点高度
$root->height = 1 + ($this->getHeight($root->left) > $this->getHeight($root->right) ? $this->getHeight($root->left) : $this->getHeight($root->right));
//平衡的维护
$balanceFactor = $this->getBalanceFactor($root);
//LL 添加元素在左儿子左侧
if ($balanceFactor > 1 && $this->getBalanceFactor($root->left) >= 0) {
$this->rightRotate($root);
}
//RR 添加元素在右儿子右侧
if ($balanceFactor < -1 && $this->getBalanceFactor($root->left) <= 0) {
$this->leftRotate($root);
}
//LR 添加元素在左儿子右侧
if ($balanceFactor > 1 && $this->getBalanceFactor($root->right) < 0) {
//先把左儿子左旋转
$root->left = $this->leftRotate($root->left);
//再把该节点右旋转
$root = $this->rightRotate($root);
}
//RL 添加元素在右儿子左侧
if ($balanceFactor < -1 && $this->getBalanceFactor($root->right) < 0) {
//先把右儿子右旋转
$root->right = $this->leftRotate($root->right);
//再把该节点左旋转
$root = $this->leftRotate($root);
}
return $root;
}
/**
* 获取节点平衡因子
* @param AVLNode $node
* @return int
*/
private function getBalanceFactor($node) {
if ($node == null) {
return 0;
}
return $this->getHeight($node->left) - $this->getHeight($node->right);
}
/**
* 判断 AVL 是否包含某个元素
* @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) { //若当前节点为空 则表示不存在元素 $e
return false;
} elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $e
return true;
} elseif ($e < $root->e) { //若 $e 小于当前节点元素，则去左儿子树递归查询是否包含节点
return $this->recursionContains($root->left, $e);
} else { //若 $e 大于当前节点元素，则去右儿子树递归查询是否包含节点
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<br>";
return;
}
echo $root->e . "<br>"; //打印当前节点元素
$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<br>";
return;
}
$this->recursionMidTraversal($root->left, $sign_num + 1);
echo $this->getSign($sign_num);//打印深度
echo $root->e . "<br>";
$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<br>";
return;
}
$this->recursionRearTraversal($root->left, $sign_num + 1);
$this->recursionRearTraversal($root->right, $sign_num + 1);
echo $this->getSign($sign_num);//打印深度
echo $root->e . "<br>";
}
/**
* 前序遍历压栈实现
*/
public function preTraversalByStack() {
$stack = new StackByLinkedList();
//将根节点压入栈
$stack->push($this->root);
while (!$stack->isEmpty()) {
//出栈
$node = $stack->pop();
if ($node != null) { //若出栈的当前节点不是空
echo $node->e . "<br>"; //先入栈
//先入栈右儿子
$stack->push($node->right);
//然后入栈左儿子
$stack->push($node->left);
} else { //若是空
echo "null<br>";
}
}
}
/**
* 中序遍历压栈实现
*/
public function midTraversalByStack() {
$stack = new StackByLinkedList();
//将根节点压入栈
$stack->push($this->root);
//循环依次出栈
$node = $stack->pop();
do {
if ($node != null) { //若出栈的当前节点不是空
//先入栈右儿子
$stack->push($node->right);
echo $node->e . "<br>"; //然后打印当前节点信息
//最后入栈左儿子
$stack->push($node->left);
} else { //若是空
echo "null<br>";
}
//继续出栈
$node = $stack->pop();
} while (!$stack->isEmpty());
}
/**
* 层序遍历实现
*/
public function tierTraversalByLinkedList() {
$queue = new QueueByLinkedList();
//将根节点入队
$queue->enqueue($this->root);
//循环依次出队
$node = $queue->dequeue();
do {
if ($node != null) { //若出栈的当前节点不是空
echo $node->e . "<br>"; //然后打印当前节点信息
$queue->enqueue($node->left);//左儿子入队
$queue->enqueue($node->right);//右儿子入队
} else { //若是空
echo "null<br>";
}
//继续出队
$node = $queue->dequeue();
} while (!$queue->isEmpty());
}
/**
* 获取最小元素
* @return mixed
*/
public function getMin() {
return $this->getMinNode($this->root)->e;
}
/**
* 获取某颗树最小元素节点
* @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;
}
/**
* 获取某颗树最大元素节点
* @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;
}
/**
* 拼接删除节点 返回新节点
*/
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;
/**
* 构造函数 初始化节点数据
* Node constructor.
* @param $e
*/
public function __construct($e) {
$this->e = $e;
}
}<?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-po...
扫码关注爱因诗贤
特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。
php介绍
PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
上一篇： 解决php mysql中文乱码问题
下一篇： php和c的区别有哪些
Tags 标签
php算法程序员扩展阅读
隐藏apache版本信息
2018-09-30 10:56:15 []CentOS 6.5安装php5.6
2018-09-30 11:36:53 []PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []Linux php: command not found
2020-02-05 01:30:13 []php 缓冲区 buffer 原理
2020-06-28 19:09:43 []PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []加个好友，技术交流
