SiroDiaz /
DataStructures
| @@ 51-99 (lines=49) @@ | ||
| 48 | *X Y Y Z |
|
| 49 | * |
|
| 50 | */ |
|
| 51 | private function rightRotation(AVLNode &$node) { |
|
| 52 | $temp = &$node->left; |
|
| 53 | $temp->parent = &$node->parent; |
|
| 54 | ||
| 55 | $node->left = &$temp->right; |
|
| 56 | if ($node->left !== null) { |
|
| 57 | $node->left->parent = &$snode; |
|
| 58 | } |
|
| 59 | ||
| 60 | $temp->right = &$node; |
|
| 61 | $node->parent = &$temp; |
|
| 62 | ||
| 63 | // temp took over node's place so now its parent should point to temp |
|
| 64 | if ($temp->parent !== null) { |
|
| 65 | if ($node === $temp->parent->left) { |
|
| 66 | $temp->parent->left = &$temp; |
|
| 67 | } else { |
|
| 68 | $temp->parent->right = &$temp; |
|
| 69 | } |
|
| 70 | } else { |
|
| 71 | $this->root = &$temp; |
|
| 72 | } |
|
| 73 | ||
| 74 | return $temp; |
|
| 75 | /* |
|
| 76 | $temp = &$node->left; |
|
| 77 | ||
| 78 | if($node->parent !== null) { |
|
| 79 | if($node->parent->right !== null) { |
|
| 80 | $node->parent->right = &$temp; |
|
| 81 | } else { |
|
| 82 | $node->parent->left = &$temp; |
|
| 83 | } |
|
| 84 | } |
|
| 85 | ||
| 86 | $temp->parent = &$node->parent; |
|
| 87 | $node->parent = &$temp; |
|
| 88 | $node->left = $temp->right; |
|
| 89 | if($node->left !== null) { |
|
| 90 | $node->left->parent = &$node; |
|
| 91 | } |
|
| 92 | $temp->right = &$node; |
|
| 93 | ||
| 94 | $this->adjustHeight($node); |
|
| 95 | $this->adjustHeight($temp); |
|
| 96 | ||
| 97 | return $temp; |
|
| 98 | */ |
|
| 99 | } |
|
| 100 | ||
| 101 | /* |
|
| 102 | * Does a right rotation. |
|
| @@ 104-151 (lines=48) @@ | ||
| 101 | /* |
|
| 102 | * Does a right rotation. |
|
| 103 | */ |
|
| 104 | private function leftRotation(AVLNode &$node) { |
|
| 105 | ||
| 106 | $temp = &$node->right; |
|
| 107 | $temp->parent = &$node->parent; |
|
| 108 | ||
| 109 | $node->right = &$temp->left; |
|
| 110 | ||
| 111 | if ($node->right !== null) { |
|
| 112 | $node->right->parent = &$node; |
|
| 113 | } |
|
| 114 | ||
| 115 | $temp->left = &$node; |
|
| 116 | $node->parent = &$temp; |
|
| 117 | ||
| 118 | // temp took over node's place so now its parent should point to temp |
|
| 119 | if ($temp->parent !== null) { |
|
| 120 | if ($node == $temp->parent->left) { |
|
| 121 | $temp->parent->left = &$temp; |
|
| 122 | } else { |
|
| 123 | $temp->parent->right = &$temp; |
|
| 124 | } |
|
| 125 | } else { |
|
| 126 | $this->root = &$temp; |
|
| 127 | } |
|
| 128 | ||
| 129 | return $temp; |
|
| 130 | /* |
|
| 131 | $temp = &$node->right; |
|
| 132 | if($node->parent !== null) { |
|
| 133 | if($node->parent->right === $node) { |
|
| 134 | $node->parent->right = &$node; |
|
| 135 | } else { |
|
| 136 | $node->parent->left = &$node; |
|
| 137 | } |
|
| 138 | } |
|
| 139 | $temp->parent = &$node->parent; |
|
| 140 | $node->parent = &$temp; |
|
| 141 | $node->right = $temp->left; |
|
| 142 | if($node->right !== null) { |
|
| 143 | $node->right->parent = &$node; |
|
| 144 | } |
|
| 145 | $temp->left = &$node; |
|
| 146 | */ |
|
| 147 | // $this->adjustHeight($node); |
|
| 148 | // $this->adjustHeight($temp); |
|
| 149 | ||
| 150 | // return $temp; |
|
| 151 | } |
|
| 152 | ||
| 153 | /** |
|
| 154 | * Double right rotation does first a left rotation of right child node |
|
