PHP二叉树（三）：红黑树
关于红黑树的原理网上的资源就挺多的，而且情况有点小复杂，所以在这里我就不再陈述了，直接上代码吧：
<!--?php
/**
* author:zhongjin
* time:2016/10/20 11:53
* description: 红黑树
*/
//结点
class Node
{
public $key;
public $parent;
public $left;
public $right;
public $IsRed; //分辨红节点或黑节点
public function __construct($key, $IsRed = TRUE)
{
$this--->key = $key;
$this->parent = NULL;
$this->left = NULL;
$this->right = NULL;
//插入结点默认是红色
$this->IsRed = $IsRed;
}
}
//红黑树
class Rbt
{
public $root;
/**
* 初始化树结构
* @param $arr 初始化树结构的数组
* @return null
*/
public function init($arr)
{
//根节点必须是黑色
$this->root = new Node($arr[0], FALSE);
for ($i = 1; $i < count($arr); $i++) {
$this->Insert($arr[$i]);
}
}
/**
* （对内）中序遍历
* @param $root （树或子树的）根节点
* @return null
*/
private function mid_order($root)
{
if ($root != NULL) {
$this->mid_order($root->left);
echo $root->key . "-" . ($root->IsRed ? 'r' : 'b') . ' ';
$this->mid_order($root->right);
}
}
/**
* （对外）中序遍历
* @param null
* @return null
*/
public function MidOrder()
{
$this->mid_order($this->root);
}
/**
* 查找树中是否存在$key对应的节点
* @param $key 待搜索数字
* @return $key对应的节点
*/
function search($key)
{
$current = $this->root;
while ($current != NULL) {
if ($current->key == $key) {
return $current;
} elseif ($current->key > $key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
//结点不存在
return $current;
}
/**
* 将以$root为根节点的最小不平衡二叉树做右旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function R_Rotate($root)
{
$L = $root->left;
if (!is_null($root->parent)) {
$P = $root->parent;
if($root == $P->left){
$P->left = $L;
}else{
$P->right = $L;
}
$L->parent = $P;
} else {
$L->parent = NULL;
}
$root->parent = $L;
$root->left = $L->right;
$L->right = $root;
//这句必须啊！
if ($L->parent == NULL) {
$this->root = $L;
}
}
/**
* 将以$root为根节点的最小不平衡二叉树做左旋处理
* @param $root（树或子树）根节点
* @return null
*/
private function L_Rotate($root)
{
$R = $root->right;
if (!is_null($root->parent)) {
$P = $root->parent;
if($root == $P->right){
$P->right = $R;
}else{
$P->left = $R;
}
$R->parent = $P;
} else {
$R->parent = NULL;
}
$root->parent = $R;
$root->right = $R->left;
$R->left = $root;
//这句必须啊！
if ($R->parent == NULL) {
$this->root = $R;
}
}
/**
* 查找树中的最小关键字
* @param $root 根节点
* @return 最小关键字对应的节点
*/
function search_min($root)
{
$current = $root;
while ($current->left != NULL) {
$current = $current->left;
}
return $current;
}
/**
* 查找树中的最大关键字
* @param $root 根节点
* @return 最大关键字对应的节点
*/
function search_max($root)
{
$current = $root;
while ($current->right != NULL) {
$current = $current->right;
}
return $current;
}
/**
* 查找某个$key在中序遍历时的直接前驱节点
* @param $x 待查找前驱节点的节点引用
* @return 前驱节点引用
*/
function predecessor($x)
{
//左子节点存在，直接返回左子节点的最右子节点
if ($x->left != NULL) {
return $this->search_max($x->left);
}
//否则查找其父节点，直到当前结点位于父节点的右边
$p = $x->parent;
//如果x是p的左孩子，说明p是x的后继，我们需要找的是p是x的前驱
while ($p != NULL && $x == $p->left) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 查找某个$key在中序遍历时的直接后继节点
* @param $x 待查找后继节点的节点引用
* @return 后继节点引用
*/
function successor($x)
{
if ($x->left != NULL) {
return $this->search_min($x->right);
}
$p = $x->parent;
while ($p != NULL && $x == $p->right) {
$x = $p;
$p = $p->parent;
}
return $p;
}
/**
* 将$key插入树中
* @param $key 待插入树的数字
* @return null
*/
public function Insert($key)
{
if (!is_null($this->search($key))) {
throw new Exception('结点' . $key . '已存在，不可插入！');
}
$root = $this->root;
$inode = new Node($key);
$current = $root;
$prenode = NULL;
//为$inode找到合适的插入位置
while ($current != NULL) {
$prenode = $current;
if ($current->key > $inode->key) {
$current = $current->left;
} else {
$current = $current->right;
}
}
$inode->parent = $prenode;
//如果$prenode == NULL， 则证明树是空树
if ($prenode == NULL) {
$this->root = $inode;
} else {
if ($inode->key < $prenode->key) {
$prenode->left = $inode;
} else {
$prenode->right = $inode;
}
}
//将它重新修正为一颗红黑树
$this->InsertFixUp($inode);
}
/**
* 对插入节点的位置及往上的位置进行颜色调整
* @param $inode 插入的节点
* @return null
*/
private function InsertFixUp($inode)
{
//情况一：需要调整条件，父节点存在且父节点的颜色是红色
while (($parent = $inode->parent) != NULL && $parent->IsRed == TRUE) {
//祖父结点：
$gparent = $parent->parent;
//如果父节点是祖父结点的左子结点，下面的else与此相反
if ($parent == $gparent->left) {
//叔叔结点
$uncle = $gparent->right;
//case1:叔叔结点也是红色
if ($uncle != NULL && $uncle->IsRed == TRUE) {
//将父节点和叔叔结点都涂黑，将祖父结点涂红
$parent->IsRed = FALSE;
$uncle->IsRed = FALSE;
$gparent->IsRed = TRUE;
//将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
$inode = $gparent;
//继续while循环，重新判断
continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
}
//case2:叔叔结点是黑色，且当前结点是右子节点
if ($inode == $parent->right) {
//以父节点作为旋转结点做左旋转处理
$this->L_Rotate($parent);
//在树中实际上已经转换，但是这里的变量的指向还没交换，
//将父节点和字节调换一下，为下面右旋做准备
$temp = $parent;
$parent = $inode;
$inode = $temp;
}
//case3:叔叔结点是黑色，而且当前结点是父节点的左子节点
$parent->IsRed = FALSE;
$gparent->IsRed = TRUE;
$this->R_Rotate($gparent);
} //如果父节点是祖父结点的右子结点，与上面完全相反
else {
//叔叔结点
$uncle = $gparent->left;
//case1:叔叔结点也是红色
if ($uncle != NULL && $uncle->IsRed == TRUE) {
//将父节点和叔叔结点都涂黑，将祖父结点涂红
$parent->IsRed = FALSE;
$uncle->IsRed = FALSE;
$gparent->IsRed = TRUE;
//将新节点指向祖父节点（现在祖父结点变红，可以看作新节点存在）
$inode = $gparent;
//继续while循环，重新判断
continue; //经过这一步之后，组父节点作为新节点存在（跳到case2）
}
//case2:叔叔结点是黑色，且当前结点是左子节点
if ($inode == $parent->left) {
//以父节点作为旋转结点做右旋转处理
$this->R_Rotate($parent);
//在树中实际上已经转换，但是这里的变量的指向还没交换，
//将父节点和字节调换一下，为下面右旋做准备
$temp = $parent;
$parent = $inode;
$inode = $temp;
}
//case3:叔叔结点是黑色，而且当前结点是父节点的右子节点
$parent->IsRed = FALSE;
$gparent->IsRed = TRUE;
$this->L_Rotate($gparent);
}
}
//情况二：原树是根节点（父节点为空），则只需将根节点涂黑
if ($inode == $this->root) {
$this->root->IsRed = FALSE;
return;
}
//情况三：插入节点的父节点是黑色，则什么也不用做
if ($inode->parent != NULL && $inode->parent->IsRed == FALSE) {
return;
}
}
/**
* （对外）删除指定节点
* @param $key 删除节点的key值
* @return null
*/
function Delete($key)
{
if (is_null($this->search($key))) {
throw new Exception('结点' . $key . "不存在，删除失败！");
}
$dnode = $this->search($key);
if ($dnode->left == NULL || $dnode->right == NULL) { #如果待删除结点无子节点或只有一个子节点，则c = dnode
$c = $dnode;
} else { #如果待删除结点有两个子节点，c置为dnode的直接后继，以待最后将待删除结点的值换为其后继的值
$c = $this->successor($dnode);
}
//为了后面颜色处理做准备
$parent = $c->parent;
//无论前面情况如何，到最后c只剩下一边子结点
if ($c->left != NULL) { //这里不会出现，除非选择的是删除结点的前驱
$s = $c->left;
} else {
$s = $c->right;
}
if ($s != NULL) { #将c的子节点的父母结点置为c的父母结点，此处c只可能有1个子节点，因为如果c有两个子节点，则c不可能是dnode的直接后继
$s->parent = $c->parent;
}
if ($c->parent == NULL) { #如果c的父母为空，说明c=dnode是根节点，删除根节点后直接将根节点置为根节点的子节点，此处dnode是根节点，且拥有两个子节点，则c是dnode的后继结点，c的父母就不会为空，就不会进入这个if
$this->root = $s;
} else if ($c == $c->parent->left) { #如果c是其父节点的左右子节点，则将c父母的左右子节点置为c的左右子节点
$c->parent->left = $s;
} else {
$c->parent->right = $s;
}
$dnode->key = $c->key;
$node = $s;
//c的结点颜色是黑色，那么会影响路径上的黑色结点的数量，必须进行调整
if ($c->IsRed == FALSE) {
$this->DeleteFixUp($node,$parent);
}
}
/**
* 删除节点后对接点周围的其他节点进行调整
* @param $key 删除节点的子节点和父节点
* @return null
*/
private function DeleteFixUp($node,$parent)
{
//如果待删结点的子节点为红色，直接将子节点涂黑
if ($node != NULL && $node->IsRed == TRUE) {
$node->IsRed = FALSE;
return;
}
//如果是根节点，那就直接将根节点置为黑色即可
while (($node == NULL || $node->IsRed == FALSE) && ($node != $this->root)) {
//node是父节点的左子节点，下面else与这里相反
if ($node == $parent->left) {
$brother = $parent->right;
//case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
//将父节点涂红，将兄弟结点涂黑，然后对父节点进行左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
if ($brother->IsRed == TRUE) {
$brother->IsRed = FALSE;
$parent->IsRed = TRUE;
$this->L_Rotate($parent);
//将情况转化为其他的情况
$brother = $parent->right; //在左旋处理后，$parent->right指向的是原来兄弟结点的左子节点
}
//以下是兄弟结点为黑色的情况
//case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
//将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
$brother->IsRed = TRUE;
$node = $parent;
$parent = $node->parent;
} else {
//case3:兄弟结点是黑色，兄弟结点的左子节点是红色，右子节点为黑色
//将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
if ($brother->right == NULL || $brother->right->IsRed == FALSE) {
$brother->IsRed = TRUE;
$brother->left->IsRed = FALSE;
$this->R_Rotate($brother);
//将情况转换为其他情况
$brother = $parent->right;
}
//case4:兄弟结点是黑色，且兄弟结点的右子节点为红色，左子节点为任意颜色
//将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点做左旋处理
$brother->IsRed = $parent->IsRed;
$parent->IsRed = FALSE;
$brother->right->IsRed = FALSE;
$this->L_Rotate($parent);
//到了第四种情况，已经是最基本的情况了，可以直接退出了
$node = $this->root;
break;
}
} //node是父节点的右子节点
else {
$brother = $parent->left;
//case1:兄弟结点颜色是红色（父节点和兄弟孩子结点都是黑色）
//将父节点涂红，将兄弟结点涂黑，然后对父节点进行右旋处理（经过这一步，情况转换为兄弟结点颜色为黑色的情况）
if ($brother->IsRed == TRUE) {
$brother->IsRed = FALSE;
$parent->IsRed = TRUE;
$this->R_Rotate($parent);
//将情况转化为其他的情况
$brother = $parent->left; //在右旋处理后，$parent->left指向的是原来兄弟结点的右子节点
}
//以下是兄弟结点为黑色的情况
//case2:兄弟结点是黑色，且兄弟结点的两个子节点都是黑色
//将兄弟结点涂红，将当前结点指向其父节点，将其父节点指向当前结点的祖父结点。
if (($brother->left == NULL || $brother->left->IsRed == FALSE) && ($brother->right == NULL || $brother->right->IsRed == FALSE)) {
$brother->IsRed = TRUE;
$node = $parent;
$parent = $node->parent;
} else {
//case3:兄弟结点是黑色，兄弟结点的右子节点是红色，左子节点为黑色
//将兄弟结点涂红，将兄弟节点的左子节点涂黑，然后对兄弟结点做左旋处理（经过这一步，情况转换为兄弟结点颜色为黑色，右子节点为红色的情况）
if ($brother->left == NULL || $brother->left->IsRed == FALSE) {
$brother->IsRed = TRUE;
$brother->right = FALSE;
$this->L_Rotate($brother);
//将情况转换为其他情况
$brother = $parent->left;
}
//case4:兄弟结点是黑色，且兄弟结点的左子节点为红色，右子节点为任意颜色
//将兄弟节点涂成父节点的颜色，再把父节点涂黑，将兄弟结点的右子节点涂黑，然后对父节点左左旋处理
$brother->IsRed = $parent->IsRed;
$parent->IsRed = FALSE;
$brother->left->IsRed = FALSE;
$this->R_Rotate($parent);
$node = $this->root;
break;
}
}
}
if ($node != NULL) {
$this->root->IsRed = FALSE;
}
}
/**
* （对内）获取树的深度
* @param $root 根节点
* @return 树的深度
*/
private function getdepth($root)
{
if ($root == NULL) {
return 0;
}
$dl = $this->getdepth($root->left);
$dr = $this->getdepth($root->right);
return ($dl > $dr ? $dl : $dr) + 1;
}
/**
* （对外）获取树的深度
* @param null
* @return null
*/
public function Depth()
{
return $this->getdepth($this->root);
}
}登录后复制
调试的时候你们可以调用中序遍历来做，我在上一篇博客中提供了PHP实现的二叉树图形化，有了视觉上的帮助就能更好的帮助我们进行调试，详细大家可以访问我的上一篇博客：《利用PHP实现二叉树的图形显示》
以上就是PHP二叉树（三）：红黑树的内容，更多相关内容请关注PHP中文网（www.php.cn）！
本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
AI Hentai Generator
免费生成ai无尽的。
热门文章
R.E.P.O.能量晶体解释及其做什么（黄色晶体）
1 个月前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
1 个月前
By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
2 周前
By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
1 个月前
By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.聊天命令以及如何使用它们
1 个月前
By 尊渡假赌尊渡假赌尊渡假赌
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
热门话题
在PHP API中说明JSON Web令牌（JWT）及其用例。
Apr 05, 2025 am 12:04 AM
JWT是一种基于JSON的开放标准，用于在各方之间安全地传输信息，主要用于身份验证和信息交换。1.JWT由Header、Payload和Signature三部分组成。2.JWT的工作原理包括生成JWT、验证JWT和解析Payload三个步骤。3.在PHP中使用JWT进行身份验证时，可以生成和验证JWT，并在高级用法中包含用户角色和权限信息。4.常见错误包括签名验证失败、令牌过期和Payload过大，调试技巧包括使用调试工具和日志记录。5.性能优化和最佳实践包括使用合适的签名算法、合理设置有效期、
解释PHP中晚期静态结合的概念。
Mar 21, 2025 pm 01:33 PM
文章讨论了PHP 5.3中引入的PHP中的晚期静态结合（LSB），从而允许静态方法的运行时分辨率调用以获得更灵活的继承。 LSB的实用应用和潜在的触摸
如何用PHP的cURL库发送包含JSON数据的POST请求？
Apr 01, 2025 pm 03:12 PM
使用PHP的cURL库发送JSON数据在PHP开发中，经常需要与外部API进行交互，其中一种常见的方式是使用cURL库发送POST�...
描述扎实的原则及其如何应用于PHP的开发。
Apr 03, 2025 am 12:04 AM
SOLID原则在PHP开发中的应用包括：1.单一职责原则（SRP）：每个类只负责一个功能。2.开闭原则（OCP）：通过扩展而非修改实现变化。3.里氏替换原则（LSP）：子类可替换基类而不影响程序正确性。4.接口隔离原则（ISP）：使用细粒度接口避免依赖不使用的方法。5.依赖倒置原则（DIP）：高低层次模块都依赖于抽象，通过依赖注入实现。
如何在系统重启后自动设置unixsocket的权限？
Mar 31, 2025 pm 11:54 PM
如何在系统重启后自动设置unixsocket的权限每次系统重启后，我们都需要执行以下命令来修改unixsocket的权限：sudo...
