红黑树

<?php //大部分代码按照自己对算法导论的伪代码的理解编写 namespace zxszl; /* 红黑树的特性: （1）每个节点或者是黑色，或者是红色。 （2）根节点是黑色。 （3）每个叶节点（NIL）是黑色。 [注意：这里叶节点，是指为空(NIL或NULL)的子节点！] （4）如果一个节点是红色的，则它的子节点必须是黑色的。 （5）从一个节点到该节点的叶节点的所有路径上包含相同数目的黑节点。 */ //参考 https://blog.csdn.net/v_JULY_v/article/details/6105630 class RedBlackNode { public $parent;//父节点 public $left; //左子节点 public $right; //右子节点 public $isRed; //红色节点或者黑色节点 /** * 这里引入两个变量，是为了方便字典数据结构 * 其中，key作为红黑树的排序依据 */ public $key; //节点值 public $value; //节点值 public function __construct () { $this->parent = null; $this->left = null; $this->right = null; $this->isRed = true; $this->key = null; $this->value = null; } } /** * 红黑树 ，左边小节点，右边大节点 */ class RedBlackTree { /** * 深度（树高度） * @param RedBlackNode $node * @return int */ static public function depth($node) { if ($node === NULL) { return 0; } $left_d = RedBlackTree::depth($node->left); $right_d = RedBlackTree::depth($node->right); return ($left_d > $right_d ? $left_d : $right_d) + 1; } /** * 最小节点 * @return RedBlackNode 最小节点 */ static public function minNode($node) { $current = $node; if ($current !== null) { while ($current->left !== null) { $current = $current->left; } } return $current; } /** * 最大节点 * @return RedBlackNode 最大节点 */ static public function maxNode($node) { $current = $node; if ($current !== null) { while ($current->right !== null) { $current = $current->right; } } return $current; } /** * 查找指定节点 * @return RedBlackNode 节点 */ public function searchNode($key) { $current = $this->rootNode; while ($current !== NULL) { if ($current->key === $key) { return $current; } elseif ($current->key > $key) { $current = $current->left; } else { $current = $current->right; } } return null; } /** * 插入节点，若$key已经存在，则替换对应节点的$value * @return RedBlackNode 插入的节点 */ public function insertNode($key,$value) { //查找节点插入时的父亲节点 $nodeParent = null; do { $tmp = $this->rootNode; while ($tmp !== null) { $nodeParent = $tmp; if ($key === $tmp->key ) {//已经存在key，不必再插入,只要替换value就可以 $tmp->value = $value; return; } else if ( $key < $tmp->key ) { $tmp = $tmp->left; } else { $tmp = $tmp->right; } } }while(0); //创建新节点,节点为红色 $node = new RedBlackNode(); // $node->isRed = true; $node->key = $key; $node->value = $value; //插入节点 $node->parent = $nodeParent; if ($nodeParent === null) { $this->rootNode = $node; } else if ($node->key < $nodeParent->key) { $nodeParent->left = $node; } else { $nodeParent->right = $node; } //修正红黑树 $this->p_insert_fixup($node); } /** * 删除节点 */ public function deleteNode ($key) { $z = $this->searchNode($key); if ( $z !== null ) //找到$key对应的节点 { //$z //待删除节点 $y = null; $x = null; ///>>>START $z不为null，那么经过操作，$y一定不为null if ($z->left === null || $z->right === null) { $y = $z; } else { $y = RedBlackTree::minNode($z->right); //$z的最小上限 } ///<<<END if ( $y->left !== null ) { $x = $y->left; } else { $x = $y->right; } //删除节点$y if ($x !== null){ $x->parent = $y->parent; } if ($y->parent === null ) { $this->rootNode = $x; } else if ( $y === $y->parent->left ) { $y->parent->left = $x; } else { $y->parent->right = $x; } $xParent = $y->parent; //如果$y不是$z，那么用$y的信息覆盖$z,这样达到删除$z的目的 if ($y !== $z) { $z->key = $y->key; $z->value = $y->value; } //如果删除的节点是黑色，则需要修正 if ($y->isRed === false) {//$y可能是$z ,也可能是$z的最小上限 $this->p_delete_fixup($x,$xParent); } } } /** * 修正红黑树 * @param RedBlackNode node 插入的节点 */ private function p_insert_fixup($node) { while ($node->parent !== null && $node->parent->isRed === true ) //如果node的父节点是红色 (node是红色) { $grandParent = $node->parent->parent; //祖父节点，一定存在 (根据红黑树性质，红色节点一定有父节点)) if ($node->parent === $grandParent->left ) { //node的父节点是左孩子 $uncle = $grandParent->right; //case1：node的父节点是红色，且叔节点是红色 if ($uncle && $uncle->isRed === true ) { $uncle->isRed = false; $node->parent->isRed = false; $grandParent->isRed = true; $node = $grandParent; continue; //经过这一步之后，组父节点作为新节点存在（跳到case2） } //case2：node的父节点是红色,叔节点是黑色，node是其父节点的右孩子 else if ($node === $node->parent->right ) { $node = $node->parent; $this->p_left_rotate($node); } //case3：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子 $node->parent->isRed = false; $grandParent->isRed = true; $this->p_right_rotate($grandParent); } else { //node的父节点是右孩子 $uncle = $grandParent->left; //case1：node的父节点是红色，且叔节点是红色 if ($uncle && $uncle->isRed === true ) { $uncle->isRed = false; $node->parent->isRed = false; $grandParent->isRed = true; $node = $grandParent; continue; //经过这一步之后，组父节点作为新节点存在（跳到case2） } //case2：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子 else if ($node === $node->parent->left ) { $node = $node->parent; $this->p_right_rotate($node); } //case3：node的父节点是红色,叔节点是黑色，node是其父节点的左孩子 $node->parent->isRed = false; $grandParent->isRed = true; $this->p_left_rotate($grandParent); } } $this->rootNode->isRed = false; } /** * 修正红黑树 * @param RedBlackNode $x * @param RedBlackNode $xParent */ private function p_delete_fixup($x,$xParent) { while ( $x !== $this->rootNode && ($x ===null || $x->isRed === false ) ) { if ($x === $xParent->left ) //$x不是根节点，那么$xParent一定存在 { $w = $xParent->right; if ($w !== null ) //若为null，则$w黑色 { //case1：$x黑, 兄弟节点$w红，父节点黑 if ($w->isRed === true ) { $w->isRed = false; $xParent->isRed = true; $this->p_left_rotate($xParent); $w = $xParent->right; //在左旋处理后，$xParent->right指向的是原来兄弟结点$w的右孩子，黑色 } //case2：$x黑色， $w是黑色，且$w两个子节点都是黑色 if ( ($w->left===null || $w->left->isRed === false) && ($w->right===null || $w->right->isRed === false) ) { $w->isRed = true; $x = $xParent; $xParent = $x->parent; } else { //case3：$x黑色，$w黑色，$w左子是红色，$w右子是黑色 if ( $w->right===null || $w->right->isRed === false ) { $w->left->isRed = false; $w->isRed = true; $this->p_right_rotate($w); $w = $xParent->right; } //case4：$x黑色，$w黑色，$w右子是红色，$w左子的颜色任意 $w->isRed = $xParent->isRed; $xParent->isRed = false; if ($w->right !== null ) { $w->right->isRed = false; } $this->p_left_rotate($xParent); $x = $this->rootNode; break;//加不加break都可以，因为下次循环条件不满足 } } } else //$x是右孩子 $x不是根节点，那么$xParent一定存在 { $w = $xParent->left; if ($w !== null ) //若为null，则$w黑色 { //case1：$x黑, 兄弟节点$w红，父节点黑 if ($w->isRed === true ) { $w->isRed = false; $xParent->isRed = true; $this->p_right_rotate($xParent); $w = $xParent->left; //在右旋处理后，$xParent->left指向的是原来兄弟结点$w的左孩子，黑色 } //case2：$x黑色， $w是黑色，且$w两个子节点都是黑色 if ( ($w->left===null || $w->left->isRed === false) && ($w->right===null || $w->right->isRed === false) ) { $w->isRed = true; $x = $xParent; $xParent = $x->parent; } else { //case3：$x黑色，$w黑色，$w左子是黑色，$w右子是红色 if ( $w->left===null || $w->left->isRed === false ) { $w->right->isRed = false; $w->isRed = true; $this->p_left_rotate($w); $w = $xParent->left; } //case4：$x黑色，$w黑色，$w左子是红色，$w右子的颜色任意 $w->isRed = $xParent->isRed; $xParent->isRed = false; if ($w->left !== null ) { $w->left->isRed = false; } $this->p_right_rotate($xParent); $x = $this->rootNode; break;//加不加break都可以，因为下次循环条件不满足 } } } } if ($x !== null ) { $x->isRed = false; } } /** * 对指定节点进行左旋操作 * 左旋中的“左”，意味着“被旋转的节点将变成（自己右孩子的）一个左节点 * node right * / \ / \ * a right ======> node c * / \ / \ * b c a b * * @param RedBlackNode $node */ private function p_left_rotate($node) { $rightChild = $node->right; //右孩子 if ($rightChild === null){ //右孩子为null，左旋结束 return; } $rightChild->parent = $node->parent; //将 “node的父亲” 设为 “rightChild的父亲” if ($rightChild->parent === null) { //情况1：如果 “rightChild的父亲” 是空节点，则将rightChild设为根节点 $this->rootNode = $rightChild; } else if ($node === $node->parent->left ) { //情况2：如果 node是它父节点的左孩子，则将rightChild设为“node的父节点的左孩子” $node->parent->left = $rightChild; } else { // 情况3：(node是它父节点的右孩子) 将rightChild设为“node的父节点的右孩子” $node->parent->right = $rightChild; } $node->parent = $rightChild; //将 “node的父节点” 设为 “rightChild” $node->right = $rightChild->left; //将 “rightChild的左孩子” 设为 “node的右孩子” if ($rightChild->left !== null) { $rightChild->left->parent = $node; //将 “node” 设为 “rightChild的左孩子的父亲” } $rightChild->left = $node; //将 “node” 设为 “rightChild的左孩子” } /** * 对指定节点进行右旋操作 * 右旋中的“右”，意味着“被旋转的节点将变成（自己左孩子的）一个右节点” * left node * / \ / \ * a node <====== left c * / \ / \ * b c a b * * @param RedBlackNode $node */ private function p_right_rotate($node) { $leftChild = $node->left; //左孩子 if ($leftChild === null) { //左孩子为null，右旋结束 return; } $leftChild->parent = $node->parent; //将 “node的父节点” 设为 “leftChild的父节点” if ($leftChild->parent === null) { // 情况1：如果 “leftChild的父亲” 是空节点，则将leftChild设为根节点 $this->rootNode = $leftChild; } else if ($node === $node->parent->left ) { // 情况2：如果 node 是它父节点的左孩子，则将leftChild设为“node的父节点的左孩子” $node->parent->left = $leftChild; } else { // 情况3：如果 node 是它父节点的右孩子，则将leftChild设为“node的父节点的右孩子” $node->parent->right = $leftChild; } $node->parent = $leftChild; //将leftChild设为“node的父节点” $node->left = $leftChild->right; //将 “leftChild的右孩子” 设为"node的左孩子" if ( $leftChild->right !== null ){ $leftChild->right->parent = $node; //将node 设为 “leftChild的右孩子的父节点” } $leftChild->right = $node; //将 "node" 设为 “leftChild的右孩子” } private $rootNode; } $rbTree = new RedBlackTree(); $testN = 10000; function testInsert( $rbTree ) { global $testN; $tmpArray = array(); for ($i = 0 ; $i < $testN ; $i++) { array_push($tmpArray,$i); } shuffle($tmpArray); for ($i = 0 ; $i < $testN ; $i++) { $k = $tmpArray[$i]; $rbTree->insertNode($k,$k); } for ($i = 0 ; $i < $testN ; $i++) { $node = $rbTree->searchNode($i); if($node === null) { echo "not found $i"; } else if ($node->value !== $i ) { $value = $node->value; echo "found $i,but value is $value"; } } } function testDelete( $rbTree ) { global $testN; $tmpArray = array(); for ($i = 0 ; $i < $testN ; $i++) { array_push($tmpArray,$i); } shuffle($tmpArray); for ($i = 0 ; $i < $testN ; $i++) { $k = $tmpArray[$i]; $rbTree->deleteNode($k); } for ($i = 0 ; $i < $testN ; $i++) { $node = $rbTree->searchNode($i); if($node !== null) { echo "found $i"; } } } testInsert($rbTree); testDelete($rbTree);