深度拆解Ardent的AVL树：4种旋转算法与删除平衡的实现原理

深度拆解Ardent的AVL树4种旋转算法与删除平衡的实现原理【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/ArdentArdent是一个面向对象的 PHP 集合库其中的AvlTree类完整实现了 AVL 树这种自平衡二叉搜索树插入和删除时自动触发4 种旋转算法左旋、右旋、左右旋、右左旋来保持树的平衡。本文带你从源码层面拆解 Ardent 的 AVL 树是如何完成旋转判断与删除后平衡修复的帮助你真正看懂 PHP 数据结构库的设计思路。为什么从 Ardent 源码学 AVL 树普通的二叉搜索树在有序插入场景下会退化成一条链表查找效率从 O(log n) 掉到 O(n)。AVL 树通过约束任意节点的左右子树高度差不超过 1来解决这个问题代价是在插入/删除时做局部旋转。Ardent 的妙处在于整棵平衡树的逻辑被拆成了三个清晰的协作层非常适合作为学习范本 层次文件职责节点层src/Collection/BinaryTree.php存储值、左右子节点缓存高度平衡层src/Collection/AvlTree.php高度差判断、4 种旋转、删除状态机遍历层src/Collection/InOrderIterator.php用中序迭代输出有序序列高度缓存机制4 种旋转算法的地基AVL 旋转的前提是知道左右子树有多高。Ardent 没有每次都递归计算高度而是在 BinaryTree.php 中给每个节点存了一个height字段并在左右子节点被替换时立即重算function recalculateHeight() { $this-height max($this-leftHeight(), $this-rightHeight()) 1; }对应实现在 BinaryTree.php。这样leftHeight()/rightHeight()都是 O(1) 读取整棵树的插入/删除时间复杂度稳定在 O(log n)。balance()旋转的决策入口每次插入或删除后递归返回途中都会调用 AvlTree.php 中的balance()方法逻辑只有三行核心判断$diff $node-leftHeight() - $node-rightHeight(); if ($diff -1) { $node $this-rotateLeft($node); // 右子树过高 } elseif ($diff 1) { $node $this-rotateRight($node); // 左子树过高 }注意细节它只处理±1以内的失衡。因为 AVL 树在递归逐层修复后到达某一层时高度差必然只可能是 -2、0、2一次旋转即可修复。4 种旋转算法逐一拆解情况一左左型Left-Left一次右旋搞定失衡节点 X 的左子节点 L又偏向左侧。此时 rotateRight() 跳过双旋分支直接执行经典右旋X L / \ / \ L C → D X / \ / \ / \ D E (D 的子树)关键三步AvlTree.php取pivot root-left()把root的左指针指向 pivot 的右子树再让 pivot 接管root最后返回新的子树根pivot。情况二右右型Right-Right一次左旋搞定完全对称失衡节点的右子节点偏向右侧时调用 rotateLeft()pivot 变为原节点的右子节点三步指针调换后子树根上移。情况三左右型Left-Right先左旋再右旋 这是最容易让新手懵的一种。当 L 偏向右侧时即 pivot 是 L 的右子节点单右旋无法平衡。rotateRight()开头会做这个检测AvlTree.php$leftHeight $leftNode-leftHeight(); $rightHeight $leftNode-rightHeight(); $diff $leftHeight - $rightHeight; if ($diff 0) { // Left-Right case $pivot $leftNode-right(); $leftNode-setRight($pivot-left()); $pivot-setLeft($leftNode); $root-setLeft($pivot); }先对 L 做一次左旋把树型从左右扭成左左随后走上面情况一的单右旋。两次旋转的组合就是传说中的Left-Right 双旋。情况四右左型Right-Left先右旋再左旋rotateLeft()开头有对称判断AvlTree.php$diff $rightNode-leftHeight() - $rightNode-rightHeight(); if ($diff 0) { // Right-Left case $pivot $rightNode-left(); ... }右子节点的左子树更高或相等先对它做一次右旋把右左扭成右右再执行单左旋。设计亮点Ardent 没有写 4 个独立方法而是让rotateRight/rotateLeft各自内嵌一种双旋的前半段用一次高度比较自动分流——代码量减半分支语义一目了然。删除平衡一个二进制状态机覆盖 4 种节点插入只需替换值删除则要腾挪节点。Ardent 在构造函数里预注册了 4 种删除策略AvlTree.php用 deleteSelectState() 把节点的子节点状态编码成 2 位二进制再查表分派状态码含义对应策略0b000无子节点deleteNoChildren()直接摘除size--0b001只有右子节点deleteSelect(right)右子树顶替0b010只有左子节点deleteSelect(left)左子树顶替0b011左右都有子节点deleteNeitherChildIsNull()编码本身只用两行位运算$state | ($node-right() ! null) 0; $state | ($node-left() ! null) 1;双孩子节点经典中序前驱替换最难的情况是0b011。deleteNeitherChildIsNull()的做法是找到左子树中最大的节点中序前驱由 BinaryTree.php 的inOrderPredecessor()沿左子节点一路向右走到底用它替换当前节点的值然后递归删除前驱本身。由于前驱必然没有右子节点问题就降级到了前面 4 种简单情况——这是教科书级的分治思路。为什么删除后树不会失重关键在 doRecursive()无论是走左子树还是右子树递归返回后都会执行return $this-balance($node)。删除引起的高度坍塌会沿着路径自底向上传播每一层都被balance()检查并按需旋转因此无论删哪个节点树最终都保持 AVL 性质。插入路径也走同一个doRecursive()matchAction换成建节点/覆盖值一套骨架兼顾增删非常优雅。快速上手使用 Ardent 的 AvlTreeuse Ardent\Collection\AvlTree; $tree new AvlTree(); // 默认使用内置比较函数 $tree-add(50); $tree-add(30); $tree-add(70); $tree-add(20); // 触发左左型右旋 echo $tree-first(); // 20最小值 echo $tree-last(); // 70最大值 foreach ($tree as $v) { // 中序迭代输出有序序列 echo $v, ; } $tree-remove(50); // 双孩子删除 自动重平衡 echo count($tree); // 3 想要降序排列构造时传入自定义比较器即可测试用例见 AvlTreeTest.php$tree new AvlTree(function ($a, $b) { return $b $a; // 交换方向即降序 });默认的升序比较器定义在 function.php 的compare()中返回 -1/0/1 三值。核心文件速查 想动手跟读建议按这个顺序打开源码平衡树主逻辑旋转 删除状态机src/Collection/AvlTree.php节点与高度缓存src/Collection/BinaryTree.php平衡树接口契约src/Collection/BinarySearchTree.php中序迭代器src/Collection/InOrderIterator.php完整行为测试含旋转前后树形注释test/Collection/BinarySearchTree/AvlTreeTest.php基于 AVL 树构建的有序集合src/Collection/SortedSet.php小结Ardent 的 AVL 树实现堪称小而美高度缓存在节点上让每次平衡判断都是 O(1)balance()统一入口 自底向上传播增删共用同一条递归骨架旋转逻辑内嵌分流rotateRight/rotateLeft各自动处理对应的一种双旋左右旋 / 右左旋4 种情况一个都不漏删除用 2 位二进制状态机查表分派 4 种子节点情况配合中序前驱替换优雅降维。读懂这 370 多行的 AvlTree.php你就掌握了 AVL 树的全部骨架也顺便学会了 PHP 中处理复杂树算法的工程化写法。【免费下载链接】ArdentA Collections library for PHP.项目地址: https://gitcode.com/gh_mirrors/ard/Ardent创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考