数据结构-PHP 红黑树(Red Black Tree)平衡原理

数据结构-PHP 红黑树(Red Black Tree)平衡原理

红黑树（Red Black Tree） 是一种自平衡的 二分搜索树，这篇文章结合 2-3树的原理来说明 红黑树 的平衡原理，红黑树 和 2-3树 在平衡原理中是等价的。

1.2-3树示意图

下图是 2-3树 的示意图，每个节点可以存放一个元素或两个元素，每个节点有 两个儿子 或 三个儿子：

Tips：2-3树是一颗绝对平衡的树。

2.2-3 树插入元素维持平衡示意图

向2-3树插入元素时，每次只需要找到不为空的叶子节点，然后进行融合，下面展示的是往 2-3树 插入元素时节点 融合 的示意图，其中有 2个儿子 的节点称为 2节点，有 3个儿子 的节点称为 3节点：

Tips：可以采用 临时三元素节点 过渡处理。

3.红黑树和 2-3 树节点等价示意图

4.红黑树和 2-3 树等价示意图

5.红黑树示意图

6.红黑树的特点

• 红黑树在二分搜索树的基础上可以保证其不会退化成链表。
• 根节点是黑色。
• 每个叶子节点（最后的空节点）是黑色。
• 若某个节点是红色的，则它的儿子节点都是黑色的。
• 从任意一个节点到叶子节点，其经过的黑色节点数量都一样。
• 红黑树和 2-3树 是等价的。
• 红黑树是保持 黑平衡 的二叉树。

7. 节点定义 PHP 代码

对于红黑树(Red Black Tree)来说，需要标记节点的颜色是红色还是黑色，需要增加 color 属性：

class RedBlackTreeNode
{public $e;public $left = null;public $right = null;public $color = null; //红色-true  黑色-falseconst RED = true;const BLACK = false;/*** 构造函数 初始化节点数据* Node constructor.* @param $e*/public function __construct($e){$this->e = $e;$this->color = self::RED;}
}

8.向红黑树中添加元素基本操作

添加元素的节点默认是 红色，红色 节点可以理解为和父亲节点 融合，下面根据具体位置情况说明，这里为了说明方便直接引入前面 2-3 树节点的概念：

8.1 向 3 节点添加元素(LL)示意图

Tips:图中包括了颜色的翻转。

8.2 向 3 节点添加元素(LR)示意图

Tips：图中剩余步骤可按照 8.1 继续操作。

8.3 向 2 节点添加元素(L)示意图

8.4 向 2 节点添加元素?示意图

8.5 LL 情况旋转

若向 3 节点(由一个黑色节点和一个红色节点组成，红色节点是黑色节点的左儿子)中添加比原来节点都小元素，需要右旋转，并改变节点颜色：

    /** 如下 15 这个节点为新增的节点，注意：需要观察标注颜色的节点颜色变化*              35($r black)                             25($m red)*            /                                        /          \*          25($m red)                             15($n black)     35($r black)*        /                    对35节点右旋转之后*    15($n red)*      对应的关系如下：*      $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;$r->color = RedBlackTreeNode::BLACK;$m->left->color = RedBlackTreeNode::BLACK;return $m;}

Tips：其中旋转之前 25 和 35 这两个节点可以看做 2-3 树中的 3 节点，15 这个元素可以看做是新增的元素，这里只列举一种情况的操作代码，其他旋转情况的操作可按照上述代码定义。

9.向红黑树中添加元素

这里只列出上述 LL 情况的添加元素操作情况，其他情况逻辑类似，若要实现，可参照这种方式：

    public function add($e){$this->root = $this->recursionAdd($e);//根节点需要设置为黑色$this->root->color = RedBlackTreeNode::BLACK;}/*** 递归向红黑树中添加元素*/private function recursionAdd($root, $e){if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息$root = new RedBlackTreeNode($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);} //若元素等于当前节点元素 则什么都不做//维护红黑树各种情况节点的翻转操作if($root->right == RedBlackTreeNode::RED && $root->left != RedBlackTreeNode::RED){$root= $this->leftRotate($root);}if($root->left == RedBlackTreeNode::RED && $root->left->left == RedBlackTreeNode::RED){$root = $this->rightRotate($root);}if($root->left == RedBlackTreeNode::RED && $root->right == RedBlackTreeNode::RED){$root = $this->flipColors($root);}return $root;}

10.完整代码

<?php
require $root . '/QueueByLinkedList/QueueByLinkedList.php';class RedBlackTree
{private $root;private $size;/*** 构造函数 初始化 RedBlackTree* BinarySearchTree constructor.*/public function __construct(){$this->root = null;$this->size;}/** 如下 45 这个节点为新增节点，注意：需要观察标注颜色的节点颜色变化*        35($r black)                              45($m black)*              \         对35节点左旋转之后             /*          45($m red)                        35($r red)**      对应的关系如下：*      $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->color = $r->color;$r->color = RedBlackTreeNode::RED;return $m;}/** 如下 15 这个节点为新增的节点，注意：需要观察标注颜色的节点颜色变化*              35($r black)                             25($m red)*            /                                        /          \*          25($m red)                             15($n black)     35($r black)*        /                    对35节点右旋转之后*    15($n red)*      对应的关系如下：*      $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;$r->color = RedBlackTreeNode::BLACK;$m->left->color = RedBlackTreeNode::BLACK;return $m;}/*** 向红黑树中添加元素* @param $e*/public function add($e){$this->root = $this->recursionAdd($e);//根节点需要设置为黑色$this->root->color = RedBlackTreeNode::BLACK;}/*** 递归向红黑树中添加元素*/private function recursionAdd($root, $e){if ($root == null) { //若节点为空则添加元素 并且返回当前节点信息$root = new RedBlackTreeNode($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);} //若元素等于当前节点元素 则什么都不做//维护红黑树各种情况节点的翻转操作if($root->right == RedBlackTreeNode::RED && $root->left != RedBlackTreeNode::RED){$root= $this->leftRotate($root);}if($root->left == RedBlackTreeNode::RED && $root->left->left == RedBlackTreeNode::RED){$root = $this->rightRotate($root);}if($root->left == RedBlackTreeNode::RED && $root->right == RedBlackTreeNode::RED){$root = $this->flipColors($root);}return $root;}/*** 颜色翻转* @param $root*/private function flipColors($root){$root->color = RedBlackTreeNode::RED;$root->left->color = RedBlackTreeNode::BLACK;$root->right->color = RedBlackTreeNode::BLACK;}/*** 判断二叉树是否为二分搜索树*/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;}/*** 中序遍历二分搜索树*/private function inOrder($root, $queue){if ($root != null) {$this->inOrder($root->left, $queue);$queue->enqueue($root->e);$this->inOrder($root->right, $queue);}}/*** 获取当前搜索树元素个数* @return mixed*/public function getSize(){return $this->size;}/*** 判断当前二叉树是否为空* @return bool*/public function isEmpty(): bool{return $this->size == 0;}/*** 判断是否包含某个元素* @param $e* @return bool*/public function contains($e): bool{return $this->recursionContains($this->root, $e);}/*** 递归判断是否包含某元素* @param $root* @param $e* @return bool*/private function recursionContains($root, $e): bool{if ($root == null) { //若当前节点为空 则表示不存在元素 $ereturn false;} elseif ($e == $root->e) { //若 $e 等于当前节点元素，则表示树包含元素 $ereturn 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;}/*** 删除元素* @param $e*/public function remove($e){$this->root = $this->recursionRemove($this->root, $e);}/*** 递归删除元素* @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 RedBlackTreeNode
{public $e;public $left = null;public $right = null;public $color = null; //红色-true  黑色-falseconst RED = true;const BLACK = false;/*** 构造函数 初始化节点数据* Node constructor.* @param $e*/public function __construct($e){$this->e = $e;$this->color = self::RED;}
}

代码仓库 ：https://gitee.com/love-for-poetry/data-structure

扫码关注爱因诗贤