SplayTreeRotations.php

<?php

/*
 * Created by: Ramy-Badr-Ahmed (https://github.com/Ramy-Badr-Ahmed) in Pull Request: #168
 * https://github.com/TheAlgorithms/PHP/pull/168
 *
 * Please mention me (@Ramy-Badr-Ahmed) in any issue or pull request addressing bugs/corrections to this file.
 * Thank you!
 */

namespace DataStructures\SplayTree;

abstract class SplayTreeRotations
{
    abstract protected function splay(?SplayTreeNode $node, int $key): ?SplayTreeNode;
    abstract protected function setRoot(SplayTreeNode $node): void;

    /**
     * Zig rotation (single right rotation).
     * Performs a right rotation on the given node.
     * A case where the node is directly a left child of its parent.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after rotation.
     */
    protected function zig(SplayTreeNode $node): SplayTreeNode
    {
        return $this->rotateRight($node);
    }

    /**
     * Zag rotation (single left rotation).
     * Performs a left rotation on the given node.
     * A case where the node is directly a right child of its parent.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after rotation.
     */
    protected function zag(SplayTreeNode $node): SplayTreeNode
    {
        return $this->rotateLeft($node);
    }

    /**
     * Zig-Zig rotation (double right rotation).
     * Performs two consecutive right rotations on the given node. The first right rotation is applied to
     * the node’s parent, and the second one to the node’s new parent (the previous grandparent).
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotations.
     */
    protected function zigZig(SplayTreeNode $node): SplayTreeNode
    {
        $node = $this->rotateRight($node);
        return $this->rotateRight($node);
    }

    /**
     * Zag-Zag rotation (double left rotation).
     * Performs two consecutive left rotations on the given node. The first left rotation is applied to
     * the node’s parent, and the second one to the node’s new parent (the previous grandparent).
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotations.
     */
    protected function zagZag(SplayTreeNode $node): SplayTreeNode
    {
        $node = $this->rotateLeft($node);
        return $this->rotateLeft($node);
    }

    /**
     * Zig-Zag rotation (left-right rotation).
     * Performs a left rotation on the left child followed by a right rotation on the node itself.
     *
     * A case when the target key is in the right subtree of the left child.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotations.
     */
    protected function zigZag(SplayTreeNode $node): SplayTreeNode
    {
        $node->left = $this->rotateLeft($node->left);
        return $this->rotateRight($node);
    }

    /**
     * Zag-Zig rotation (right-left rotation).
     * Performs a right rotation on the right child followed by a left rotation on the node itself.
     *
     * A case when the target key is in the left subtree of the right child.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotations.
     */
    protected function zagZig(SplayTreeNode $node): SplayTreeNode
    {
        $node->right = $this->rotateRight($node->right);
        return $this->rotateLeft($node);
    }

    /**
     * Rotates the given node to the left, bringing its right child up to take its place.
     * The left subtree of the node's right child will become the new right subtree of the node.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotation (the former right child).
     */
    private function rotateLeft(SplayTreeNode $node): SplayTreeNode
    {
        $rightChild = $node->right;

        if ($rightChild === null) {
            return $node; // No rotation possible
        }

        $node->right = $rightChild->left;

        if ($rightChild->left !== null) {
            $rightChild->left->parent = $node;
        }

        $rightChild->parent = $node->parent;

        if ($node->parent === null) {
            static::setRoot($rightChild);
        } elseif ($node === $node->parent->left) {
            $node->parent->left = $rightChild;
        } else {
            $node->parent->right = $rightChild;
        }

        $rightChild->left = $node;
        $node->parent = $rightChild;

        return $rightChild;
    }

    /**
     * Rotates the given node to the right, bringing its left child up to take its place.
     * The right subtree of the node's left child will become the new left subtree of the node.
     *
     * @param SplayTreeNode $node The node to be rotated.
     * @return SplayTreeNode The new root of the subtree after the rotation (the former left child).
     */
    private function rotateRight(SplayTreeNode $node): SplayTreeNode
    {
        $leftChild = $node->left;

        if ($leftChild === null) {
            return $node;       // No rotation possible
        }

        $node->left = $leftChild->right;

        if ($leftChild->right !== null) {
            $leftChild->right->parent = $node;
        }

        $leftChild->parent = $node->parent;

        if ($node->parent === null) {
            static::setRoot($leftChild);
        } elseif ($node === $node->parent->right) {
            $node->parent->right = $leftChild;
        } else {
            $node->parent->left = $leftChild;
        }

        $leftChild->right = $node;
        $node->parent = $leftChild;

        return $leftChild;
    }
}