二叉树算法 - 平衡二叉树（AVL）的实现代码和算法复杂度

- 8 mins
PHP 数据结构与算法 二叉树算法

数据结构与算法系列（三十四）

下面我们将上一篇分享中演示的平衡二叉树构建示例转化为 PHP 代码。

平衡二叉树节点类

我们还是使用二叉链表来实现二叉树的存储，对应的节点类如下：

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

public function __construct($data)
{
    $this->data = $data;
} }

和普通二叉树节点相比，新增了一个 $bf 属性用于存放平衡因子，以及一个 $parent 属性用于存放父级节点。

平衡二叉树插入节点实现

平衡二叉树也是二叉排序树，所以查找实现和二叉排序树一样。下面我们来实现最关键的插入节点算法，我们创建了一个新的 AVLTree 类用来实现平衡二叉树的相关操作，编写新增节点相关方法如下：

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);
midOrderTraverse($avlTree->getTree());  // 中序遍历生成的二叉树看是否是二叉排序树
print_r($avlTree->getTree());           // 以数组形式打印构建的二叉树看是否是平衡二叉树

我们以上一篇分享的示例数据为例，通过上述插入节点代码将这些数据插入到二叉树中，看最终生成的二叉树是否是平衡二叉树。结果符合我们的预期，构建的二叉树和下面这个二叉树一模一样：

说明我们成功构建出了平衡二叉树。

平衡二叉树的节点删除也要不断去判断删除节点后是否还满足平衡二叉树的要求，感兴趣的同学可以去参考节点插入逻辑自行实现下。

平衡二叉树的算法复杂度

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

Related Posts

rss facebook twitter github gitlab youtube mail spotify lastfm instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora quora