PHP代码实现平衡二叉树

发布时间：2021-06-22 13:58:00 作者：chen
来源：亿速云阅读：290

# PHP代码实现平衡二叉树

## 目录
1. [平衡二叉树概述](#平衡二叉树概述)
2. [平衡二叉树的核心概念](#平衡二叉树的核心概念)
3. [PHP实现平衡二叉树节点类](#php实现平衡二叉树节点类)
4. [平衡因子与旋转操作](#平衡因子与旋转操作)
5. [插入操作的PHP实现](#插入操作的php实现)
6. [删除操作的PHP实现](#删除操作的php实现)
7. [查找操作的PHP实现](#查找操作的php实现)
8. [遍历操作的PHP实现](#遍历操作的php实现)
9. [完整平衡二叉树PHP类](#完整平衡二叉树php类)
10. [性能分析与优化](#性能分析与优化)
11. [实际应用场景](#实际应用场景)
12. [与其他数据结构的比较](#与其他数据结构的比较)
13. [常见问题与解决方案](#常见问题与解决方案)
14. [单元测试与验证](#单元测试与验证)
15. [总结与扩展](#总结与扩展)

## 平衡二叉树概述

平衡二叉树（Balanced Binary Tree），特别是AVL树（由发明者Adelson-Velsky和Landis命名），是一种自平衡的二叉搜索树。在AVL树中，任何节点的两个子树的高度差不超过1，这种严格的平衡条件确保了树的操作时间复杂度保持在O(log n)级别。

### 为什么需要平衡二叉树？
- 普通二叉搜索树在极端情况下会退化为链表（例如按顺序插入数据）
- 平衡二叉树通过自动调整保持平衡，确保高效操作
- 适用于需要频繁插入、删除和查找的场景

## 平衡二叉树的核心概念

### 基本性质
1. **二叉搜索树性质**：左子树所有节点值 < 根节点值 < 右子树所有节点值
2. **平衡性质**：对于每个节点，左右子树高度差的绝对值不超过1（平衡因子∈[-1,0,1]）

### 关键术语
- **平衡因子(Balance Factor)**：左子树高度 - 右子树高度
- **旋转操作(Rotation)**：通过局部调整恢复平衡的操作
- **高度(Height)**：节点到最深叶子节点的最长路径长度

## PHP实现平衡二叉树节点类

```php
<?php
class AVLNode {
    public $value;
    public $left;
    public $right;
    public $height;
    
    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
        $this->height = 1; // 新节点初始高度为1
    }
}

节点类说明

value：存储节点值
left：指向左子节点的指针
right：指向右子节点的指针
height：记录当前节点的高度（用于计算平衡因子）

平衡因子与旋转操作

平衡因子计算

private function getBalanceFactor($node) {
    if ($node === null) {
        return 0;
    }
    return $this->getHeight($node->left) - $this->getHeight($node->right);
}

四种旋转情况

1. 左旋转（LL型不平衡）

private function leftRotate($x) {
    $y = $x->right;
    $T2 = $y->left;
    
    // 执行旋转
    $y->left = $x;
    $x->right = $T2;
    
    // 更新高度
    $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;
    $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;
    
    return $y;
}

2. 右旋转（RR型不平衡）

private function rightRotate($y) {
    $x = $y->left;
    $T2 = $x->right;
    
    // 执行旋转
    $x->right = $y;
    $y->left = $T2;
    
    // 更新高度
    $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;
    $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;
    
    return $x;
}

3. 左右旋转（LR型不平衡）

private function leftRightRotate($node) {
    $node->left = $this->leftRotate($node->left);
    return $this->rightRotate($node);
}

4. 右左旋转（RL型不平衡）

private function rightLeftRotate($node) {
    $node->right = $this->rightRotate($node->right);
    return $this->leftRotate($node);
}

插入操作的PHP实现

public function insert($value) {
    $this->root = $this->insertNode($this->root, $value);
}

private function insertNode($node, $value) {
    // 1. 执行标准BST插入
    if ($node === null) {
        return new AVLNode($value);
    }
    
    if ($value < $node->value) {
        $node->left = $this->insertNode($node->left, $value);
    } elseif ($value > $node->value) {
        $node->right = $this->insertNode($node->right, $value);
    } else {
        return $node; // 不允许重复值
    }
    
    // 2. 更新节点高度
    $node->height = 1 + max($this->getHeight($node->left), 
                          $this->getHeight($node->right));
    
    // 3. 获取平衡因子判断是否平衡
    $balance = $this->getBalanceFactor($node);
    
    // 4. 处理不平衡情况
    // 左左情况
    if ($balance > 1 && $value < $node->left->value) {
        return $this->rightRotate($node);
    }
    
    // 右右情况
    if ($balance < -1 && $value > $node->right->value) {
        return $this->leftRotate($node);
    }
    
    // 左右情况
    if ($balance > 1 && $value > $node->left->value) {
        return $this->leftRightRotate($node);
    }
    
    // 右左情况
    if ($balance < -1 && $value < $node->right->value) {
        return $this->rightLeftRotate($node);
    }
    
    return $node;
}

删除操作的PHP实现

public function delete($value) {
    $this->root = $this->deleteNode($this->root, $value);
}

private function deleteNode($node, $value) {
    // 1. 执行标准BST删除
    if ($node === null) {
        return $node;
    }
    
    if ($value < $node->value) {
        $node->left = $this->deleteNode($node->left, $value);
    } elseif ($value > $node->value) {
        $node->right = $this->deleteNode($node->right, $value);
    } else {
        // 找到要删除的节点
        // 情况1: 只有一个子节点或没有子节点
        if (($node->left === null) || ($node->right === null)) {
            $temp = $node->left ?? $node->right;
            
            // 无子节点情况
            if ($temp === null) {
                $temp = $node;
                $node = null;
            } else {
                // 有一个子节点情况
                $node = $temp;
            }
        } else {
            // 情况2: 有两个子节点
            // 获取中序后继节点（右子树的最小值）
            $temp = $this->minValueNode($node->right);
            
            // 复制中序后继节点的值
            $node->value = $temp->value;
            
            // 删除中序后继节点
            $node->right = $this->deleteNode($node->right, $temp->value);
        }
    }
    
    // 如果树只有一个节点则直接返回
    if ($node === null) {
        return $node;
    }
    
    // 2. 更新节点高度
    $node->height = 1 + max($this->getHeight($node->left),
                           $this->getHeight($node->right));
    
    // 3. 获取平衡因子判断是否平衡
    $balance = $this->getBalanceFactor($node);
    
    // 4. 处理不平衡情况
    // 左左情况
    if ($balance > 1 && $this->getBalanceFactor($node->left) >= 0) {
        return $this->rightRotate($node);
    }
    
    // 左右情况
    if ($balance > 1 && $this->getBalanceFactor($node->left) < 0) {
        return $this->leftRightRotate($node);
    }
    
    // 右右情况
    if ($balance < -1 && $this->getBalanceFactor($node->right) <= 0) {
        return $this->leftRotate($node);
    }
    
    // 右左情况
    if ($balance < -1 && $this->getBalanceFactor($node->right) > 0) {
        return $this->rightLeftRotate($node);
    }
    
    return $node;
}

private function minValueNode($node) {
    $current = $node;
    while ($current->left !== null) {
        $current = $current->left;
    }
    return $current;
}

查找操作的PHP实现

public function search($value) {
    return $this->searchNode($this->root, $value);
}

private function searchNode($node, $value) {
    if ($node === null) {
        return false;
    }
    
    if ($value < $node->value) {
        return $this->searchNode($node->left, $value);
    } elseif ($value > $node->value) {
        return $this->searchNode($node->right, $value);
    } else {
        return true;
    }
}

遍历操作的PHP实现

中序遍历（升序输出）

public function inOrder() {
    $result = [];
    $this->inOrderTraversal($this->root, $result);
    return $result;
}

private function inOrderTraversal($node, &$result) {
    if ($node !== null) {
        $this->inOrderTraversal($node->left, $result);
        $result[] = $node->value;
        $this->inOrderTraversal($node->right, $result);
    }
}

前序遍历

public function preOrder() {
    $result = [];
    $this->preOrderTraversal($this->root, $result);
    return $result;
}

private function preOrderTraversal($node, &$result) {
    if ($node !== null) {
        $result[] = $node->value;
        $this->preOrderTraversal($node->left, $result);
        $this->preOrderTraversal($node->right, $result);
    }
}

后序遍历

public function postOrder() {
    $result = [];
    $this->postOrderTraversal($this->root, $result);
    return $result;
}

private function postOrderTraversal($node, &$result) {
    if ($node !== null) {
        $this->postOrderTraversal($node->left, $result);
        $this->postOrderTraversal($node->right, $result);
        $result[] = $node->value;
    }
}

层次遍历（广度优先）

public function levelOrder() {
    $result = [];
    if ($this->root === null) {
        return $result;
    }
    
    $queue = new SplQueue();
    $queue->enqueue($this->root);
    
    while (!$queue->isEmpty()) {
        $node = $queue->dequeue();
        $result[] = $node->value;
        
        if ($node->left !== null) {
            $queue->enqueue($node->left);
        }
        if ($node->right !== null) {
            $queue->enqueue($node->right);
        }
    }
    
    return $result;
}

完整平衡二叉树PHP类

”`php <?php class AVLTree { private $root;

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

// 获取节点高度
private function getHeight($node) {
    return $node === null ? 0 : $node->height;
}

// 计算平衡因子
private function getBalanceFactor($node) {
    if ($node === null) {
        return 0;
    }
    return $this->getHeight($node->left) - $this->getHeight($node->right);
}

// 右旋转
private function rightRotate($y) {
    $x = $y->left;
    $T2 = $x->right;

    $x->right = $y;
    $y->left = $T2;

    $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;
    $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;

    return $x;
}

// 左旋转
private function leftRotate($x) {
    $y = $x->right;
    $T2 = $y->left;

    $y->left = $x;
    $x->right = $T2;

    $x->height = max($this->getHeight($x->left), $this->getHeight($x->right)) + 1;
    $y->height = max($this->getHeight($y->left), $this->getHeight($y->right)) + 1;

    return $y;
}

// 插入操作
public function insert($value) {
    $this->root = $this->insertNode($this->root, $value);
}

private function insertNode($node, $value) {
    // 标准BST插入
    if ($node === null) {
        return new AVLNode($value);
    }

    if ($value < $node->value) {
        $node->left = $this->insertNode($node->left, $value);
    } elseif ($value > $node->value) {
        $node->right = $this->insertNode($node->right, $value);
    } else {
        return $node; // 不允许重复值
    }

    // 更新高度
    $node->height = 1 + max($this->getHeight($node->left), 
                          $this->getHeight($node->right));

    // 获取平衡因子
    $balance = $this->getBalanceFactor($node);

    // 处理不平衡情况
    // 左左情况
    if ($balance > 1 && $value < $node->left->value) {
        return $this->rightRotate($node);
    }

    // 右右情况
    if ($balance < -1 && $value > $node->right->value) {
        return $this->leftRotate($node);
    }

    // 左右情况
    if ($balance > 1 && $value > $node->left->value) {
        $node->left = $this->leftRotate($node->left);
        return $this->rightRotate($node);
    }

    // 右左情况
    if ($balance < -1 && $value < $node->right->value) {
        $node->right = $this->rightRotate($node->right);
        return $this->leftRotate($node);
    }

    return $node;
}

// 删除操作
public function delete($value) {
    $this->root = $this->deleteNode($this->root, $value);
}

private function deleteNode($node, $value) {
    // 标准BST删除
    if ($node === null) {
        return $node;
    }

    if ($value < $node->value) {
        $node->left = $this->deleteNode($node->left, $value);
    } elseif ($value > $node->value) {
        $node->right = $this->deleteNode($node->right, $value);
    } else {
        // 找到要删除的节点
        if (($node->left === null) || ($node->right === null)) {
            $temp = $node->left ?? $node->right;

            if ($temp === null) {
                $temp = $node;
                $node = null;
            } else {
                $node = $temp;
            }
        } else {
            $temp = $this->minValueNode($node->right);
            $node->value = $temp->value;
            $node->right = $this->deleteNode($node->right, $temp->value);
        }
    }

    if ($node === null) {
        return $node;
    }

    // 更新高度
    $node->height = 1 + max($this->getHeight($node->left),
                           $this->getHeight($node->right));

    // 获取平衡因子
    $balance = $this->getBalanceFactor($node);

    // 处理不平衡情况
    // 左左情况
    if ($balance > 1 && $this->getBalanceFactor($node->left) >= 0) {
        return $this->rightRotate($node);
    }

    // 左右情况
    if ($balance > 1 && $this->getBalanceFactor($node->left) < 0) {
        $node->left = $this->leftRotate($node->left);
        return $this->rightRotate($node);
    }

    // 右右情况
    if ($balance < -1 && $this->getBalanceFactor($node->right) <= 0) {
        return $this->leftRotate($node);
    }

    // 右

PHP代码实现平衡二叉树

节点类说明

平衡因子与旋转操作

平衡因子计算

四种旋转情况

1. 左旋转（LL型不平衡）

2. 右旋转（RR型不平衡）

3. 左右旋转（LR型不平衡）

4. 右左旋转（RL型不平衡）

插入操作的PHP实现

删除操作的PHP实现

查找操作的PHP实现

遍历操作的PHP实现

中序遍历（升序输出）

前序遍历

后序遍历

层次遍历（广度优先）

完整平衡二叉树PHP类

相关阅读