平衡二叉树(二)

平衡二叉树(二)

平衡二叉树的旋转规则

平衡因子BF的值大于1时,右旋,小于-1时左旋,如果最小不平衡子树的BF值和其子树的BF值符号相反时,需要先将子树进行旋转使两者 BF 值符号相同,再旋转最小不平衡子树。我们将单纯的左旋、右旋叫做单旋处理,将需要两次旋转处理的操作叫做双旋处理。

代码

class AVLNode
{
public $data; // 节点数据
public $left = null; // 左子结点
public $right = null; // 右子节点
public $bf = 0; // 平衡因子BF
public $parent = null; // 存储父节点

public function __construct($data)
{
$this->data = $data;
}
}
class AVLTree
{
/**
* 根节点
* @var AVLNode
*/
private $root;

const LH = 1; // 左子树高(高度差)
const EH = 0; // 等高
const RH = -1; // 右子树高(高度差)

public function getTree()
{
return $this->root;
}

/**
* @param int $data
*/
public function insert(int $data)
{
$this->insert_node($data, $this->root);
}

/**
* 插入节点
* @param int $data
* @param AVLNode $tree
* @return bool
*/
protected function insert_node(int $data, &$tree)
{

if (!$tree) {
$tree = new AVLNode($data);
$tree->bf = self::EH;
return true;
}

//如果插入的数据小于当前数据,则左节点
if ($data < $tree->data) {
//把插入的数据和父节点的左子节点比较,如果返回为真,则说明父节点的左节点为空.
if (!$this->insert_node($data, $tree->left)) {
return false;
} else {
if (empty($tree->left->parent)) {
$tree->left->parent = $tree;
}
switch ($tree->bf) {
case self::LH:
$this->left_balance($tree);
return false;
case self::EH:
$tree->bf = self::LH;
return true;
case self::RH:
$tree->bf = self::EH;
return false;
}
}
} 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 AVLNode $tree
*/
protected function right_rotate(&$tree)
{
$subTree = $tree->left; // 将子树的左节点作为新的子树根节点
if ($tree->parent) {
$subTree->parent = $tree->parent; // 更新新子树根节点的父节点
$left = false;
if ($tree->parent->left == $tree) {
$left = true;
}
} else {
$subTree->parent = null;
}
$tree->left = $subTree->right; // 将原来左节点的右子树挂到老的根节点的左子树
$tree->parent = $subTree;
$subTree->right = $tree; // 将老的根节点作为新的根节点的右子树
$tree = $subTree;
if (!$tree->parent) {
$this->root = $tree;
} else {
// 更新老的子树根节点父节点指针指向新的根节点
if ($left) {
$tree->parent->left = $tree;
} else {
$tree->parent->right = $tree;
}
}
}

/**
* 左旋操作
* @param AVLNode $tree
*/
protected function left_rotate(&$tree)
{
$subTree = $tree->right; // 逻辑和右旋正好相反
$oldTree = clone $tree;
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;
}
}
}

/**
* 左子树平衡旋转处理
* @param AVLNode $tree
*/
protected function left_balance(&$tree)
{
$subTree = $tree->left;
switch ($subTree->bf) {
case self::LH:
// 新插入节点在左子节点的左子树上要做右单旋处理
$tree->bf = $subTree->bf = self::EH;
$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::EH:
$tree->bf = $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);
}
}

/**
* 右子树平衡旋转处理
*/
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);
print_r($avlTree->getTree());

总结

二叉排序树的插入、删除、查找时提到,最理想的情况下,时间复杂度是 O(logn),而平衡二叉树就是这种理想情况,虽然平衡二叉树性能是最好的,也是最稳定的,但是这套算法实现起来比较复杂,每次插入节点和删除节点都需要判断剩下节点构成的二叉排序树是否满足平衡二叉树的要求,如果不满足需要做相应的左旋右旋处理,维护成本高,因此,在工程实践上,我们更多时候使用的是红黑树这种二叉排序树,它是一种不严格的平衡二叉树,实现起来更加简单,性能也接近严格的平衡二叉树,