SiroDiaz /
DataStructures
| @@ 48-96 (lines=49) @@ | ||
| 45 | * rotated. |
|
| 46 | * @return DataStructures\Trees\Nodes\AVLNode |
|
| 47 | */ |
|
| 48 | private function rightRotation(AVLNode &$node) { |
|
| 49 | $temp = &$node->left; |
|
| 50 | $temp->parent = &$node->parent; |
|
| 51 | ||
| 52 | $node->left = &$temp->right; |
|
| 53 | if ($node->left !== null) { |
|
| 54 | $node->left->parent = &$snode; |
|
| 55 | } |
|
| 56 | ||
| 57 | $temp->right = &$node; |
|
| 58 | $node->parent = &$temp; |
|
| 59 | ||
| 60 | // temp took over node's place so now its parent should point to temp |
|
| 61 | if ($temp->parent !== null) { |
|
| 62 | if ($node === $temp->parent->left) { |
|
| 63 | $temp->parent->left = &$temp; |
|
| 64 | } else { |
|
| 65 | $temp->parent->right = &$temp; |
|
| 66 | } |
|
| 67 | } else { |
|
| 68 | $this->root = &$temp; |
|
| 69 | } |
|
| 70 | ||
| 71 | return $temp; |
|
| 72 | } |
|
| 73 | ||
| 74 | /** |
|
| 75 | * Does a right rotation. |
|
| 76 | * |
|
| 77 | * @param DataStructures\Trees\Nodes\AVLNode $node The node to be |
|
| 78 | * rotated. |
|
| 79 | * @return DataStructures\Trees\Nodes\AVLNode |
|
| 80 | */ |
|
| 81 | private function leftRotation(AVLNode &$node) { |
|
| 82 | ||
| 83 | $temp = &$node->right; |
|
| 84 | $temp->parent = &$node->parent; |
|
| 85 | ||
| 86 | $node->right = &$temp->left; |
|
| 87 | ||
| 88 | if ($node->right !== null) { |
|
| 89 | $node->right->parent = &$node; |
|
| 90 | } |
|
| 91 | ||
| 92 | $temp->left = &$node; |
|
| 93 | $node->parent = &$temp; |
|
| 94 | ||
| 95 | // temp took over node's place so now its parent should point to temp |
|
| 96 | if ($temp->parent !== null) { |
|
| 97 | if ($node == $temp->parent->left) { |
|
| 98 | $temp->parent->left = &$temp; |
|
| 99 | } else { |
|
| @@ 81-128 (lines=48) @@ | ||
| 78 | * rotated. |
|
| 79 | * @return DataStructures\Trees\Nodes\AVLNode |
|
| 80 | */ |
|
| 81 | private function leftRotation(AVLNode &$node) { |
|
| 82 | ||
| 83 | $temp = &$node->right; |
|
| 84 | $temp->parent = &$node->parent; |
|
| 85 | ||
| 86 | $node->right = &$temp->left; |
|
| 87 | ||
| 88 | if ($node->right !== null) { |
|
| 89 | $node->right->parent = &$node; |
|
| 90 | } |
|
| 91 | ||
| 92 | $temp->left = &$node; |
|
| 93 | $node->parent = &$temp; |
|
| 94 | ||
| 95 | // temp took over node's place so now its parent should point to temp |
|
| 96 | if ($temp->parent !== null) { |
|
| 97 | if ($node == $temp->parent->left) { |
|
| 98 | $temp->parent->left = &$temp; |
|
| 99 | } else { |
|
| 100 | $temp->parent->right = &$temp; |
|
| 101 | } |
|
| 102 | } else { |
|
| 103 | $this->root = &$temp; |
|
| 104 | } |
|
| 105 | ||
| 106 | return $temp; |
|
| 107 | } |
|
| 108 | ||
| 109 | /** |
|
| 110 | * Double right rotation does first a left rotation of right child node |
|
| 111 | * that detects the imbalance and finally does a right rotation |
|
| 112 | * in the subtree root that detects the imbalance. |
|
| 113 | * Case Right-Left. |
|
| 114 | * |
|
| 115 | * @param DataStructures\Trees\Nodes\AVLNode $node The node to be |
|
| 116 | * rotated. |
|
| 117 | * @return DataStructures\Trees\Nodes\AVLNode |
|
| 118 | */ |
|
| 119 | private function doubleRightRotation(AVLNode &$node) { |
|
| 120 | $this->leftRotation($node->left); |
|
| 121 | return $this->rightRotation($node); |
|
| 122 | } |
|
| 123 | ||
| 124 | /** |
|
| 125 | * Double left rotation does first a right rotation of left child node |
|
| 126 | * that detects the imbalance and finally does a left rotation |
|
| 127 | * in the subtree root that detects the imbalance. |
|
| 128 | * Case Left-Right. |
|
| 129 | * |
|
| 130 | * @param DataStructures\Trees\Nodes\AVLNode $node The node to be |
|
| 131 | * rotated. |
|
