SiroDiaz /
DataStructures
| @@ 51-74 (lines=24) @@ | ||
| 48 | *X Y Y Z |
|
| 49 | * |
|
| 50 | */ |
|
| 51 | private function rightRotation(AVLNode $node) { |
|
| 52 | $temp = &$node->left; |
|
| 53 | ||
| 54 | if($node->parent !== null) { |
|
| 55 | if($node->parent->right !== null) { |
|
| 56 | $node->parent->right = &$temp; |
|
| 57 | } else { |
|
| 58 | $node->parent->left = &$temp; |
|
| 59 | } |
|
| 60 | } |
|
| 61 | ||
| 62 | $temp->parent = &$node->parent; |
|
| 63 | $node->parent = &$temp; |
|
| 64 | $node->left = $temp->right; |
|
| 65 | if($node->left !== null) { |
|
| 66 | $node->left->parent = &$node; |
|
| 67 | } |
|
| 68 | $temp->right = &$node; |
|
| 69 | ||
| 70 | $this->adjustHeight($node); |
|
| 71 | $this->adjustHeight($temp); |
|
| 72 | ||
| 73 | return $temp; |
|
| 74 | } |
|
| 75 | ||
| 76 | /* Does a right rotation. |
|
| 77 | * k2 k1 |
|
| @@ 83-104 (lines=22) @@ | ||
| 80 | * / \ / \ |
|
| 81 | * Y Z X Y |
|
| 82 | */ |
|
| 83 | private function leftRotation(AVLNode $node) { |
|
| 84 | $temp = &$node->right; |
|
| 85 | if($node->parent !== null) { |
|
| 86 | if($node->parent->right === $node) { |
|
| 87 | $node->parent->right = &$node; |
|
| 88 | } else { |
|
| 89 | $node->parent->left = &$node; |
|
| 90 | } |
|
| 91 | } |
|
| 92 | $temp->parent = &$node->parent; |
|
| 93 | $node->parent = &$temp; |
|
| 94 | $node->right = $temp->left; |
|
| 95 | if($node->right !== null) { |
|
| 96 | $node->right->parent = &$node; |
|
| 97 | } |
|
| 98 | $temp->left = &$node; |
|
| 99 | ||
| 100 | $this->adjustHeight($node); |
|
| 101 | $this->adjustHeight($temp); |
|
| 102 | ||
| 103 | return $temp; |
|
| 104 | } |
|
| 105 | ||
| 106 | /** |
|
| 107 | * Double right rotation does first a left rotation of right child node |
|
