AVLTree::rightRotation() - Code Metrics - Inspection of "added a condition that fixes right rotation" - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 5d2724...f24b80 )

by Siro Díaz

created 2017-06-27 11:34 UTC

AVLTree::rightRotation() B

↳ Parent: AVLTree

Complexity

Conditions	4
Paths	6

Size

Total Lines	24
Code Lines	16

Duplication

Lines	24
Ratio	100 %

Importance

Changes	3
Bugs	1	Features	1

Metric	Value
c	3
b	1
f	1
dl	24
loc	24
rs	8.6845
cc	4
eloc	16
nc	6
nop	1

<?php
/**
 * DataStructures for PHP
 *
 * @link      https://github.com/SiroDiaz/DataStructures
 * @copyright Copyright (c) 2017 Siro Díaz Palazón
 * @license   https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
 */
namespace DataStructures\Trees;

use DataStructures\Trees\BinaryTreeAbstract;
use DataStructures\Trees\Nodes\AVLNode;

/**
 * AVLTree
 *
 * This class is an implementation of a AVL tree. It has as main feature that access,
 * insertion and deletion is O(log n). This is like a BST but it has a slightly difference
 * in nodes: contains a height attribute, used to detect when is needed to rebalance the
 * tree to keep the O(log n).
 *
 * @author Siro Diaz Palazon <[email protected]>
 */
class AVLTree extends BinaryTreeAbstract {
    
    /**
     * Creates a AVLNode.
     *
     * @param int|string $key the key used to store.
     * @param mixed $data the data.
     * @param DataStructures\Trees\Nodes\AVLNode|null $parent the parent node.
     * @param DataStructures\Trees\Nodes\AVLNode|null $left the left child node.
     * @param DataStructures\Trees\Nodes\AVLNode|null $right the right child node.
     *
     * @return DataStructures\Trees\Nodes\AVLNode the new node created.
     */
    public function createNode($key, $data, $parent = null, $left = null, $right = null) {
        return new AVLNode($key, $data, $parent, $left, $right);
    }

    /**
     * Does a right rotation.
     * Example, rotate Y
     *    k2                   k1
     *   /  \                 /  \
     *  k1   Z     ==>       X   k2
     * / \                      /  \
     *X   Y                    Y    Z
     *
     */
    private function rightRotation(AVLNode $node) {

        $temp = &$node->left;

        if($node->parent !== null) {
            if($node->parent->right !== null) {
                $node->parent->right = &$temp;
            } else {
                $node->parent->left = &$temp;
            }
        }

        $temp->parent = &$node->parent;
        $node->parent = &$temp;
        $node->left = $temp->right;
        if($node->left !== null) {
            $node->left->parent = &$node;
        }
        $temp->right = &$node;

        $this->adjustHeight($node);
        $this->adjustHeight($temp);

        return $temp;
    }

    /*  Does a right rotation.
     *    k2                       k1
     *  /  \                     /  \
     * X    k1         ==>      k2   Z
     *     /  \                /  \
     *    Y    Z              X    Y
     */
    private function leftRotation(AVLNode $node) {

        $temp = &$node->right;
        if($node->parent !== null) {
            if($node->parent->right === $node) {
                $node->parent->right = &$node;
            } else {
                $node->parent->left = &$node;
            }
        }
        $temp->parent = &$node->parent;
        $node->parent = &$temp;
        $node->right = $temp->left;
        if($node->right !== null) {
            $node->right->parent = &$node;
        }
        $temp->left = &$node;

        $this->adjustHeight($node);
        $this->adjustHeight($temp);

        return $temp;
    }

    /**
     * Double right rotation does first a left rotation of right child node
     * that detects the imbalance and finally does a right rotation
     * in the subtree root that detects the imbalance.
     * Case Right-Left.
     */
    private function doubleRightRotation(AVLNode $node) {
        $this->leftRotation($node->right);
        $this->rightRotation($node);
    }

    /**
     * Double left rotation does first a right rotation of left child node
     * that detects the imbalance and finally does a left rotation
     * in the subtree root that detects the imbalance.
     * Case Left-Right.
     */
    private function doubleLeftRotation(AVLNode $node) {
        $this->rightRotation($node->left);
        $this->leftRotation($node);
    }

    public function put($key, $data, $update = false) {
        $nodeInserted = parent::put($key, $data, $update);
$myVar = 'Value';
$higher = false;

if (rand(1, 6) > 3) {
    $higher = true;
} else {
    $higher = false;
}
    }

    private function adjustHeight(AVLNode $node) {
        $node->height = 1 + max($node->left->height, $node->right->height);
    }
}

1		<?php
2		/**
3		* DataStructures for PHP
4		*
5		* @link https://github.com/SiroDiaz/DataStructures
6		* @copyright Copyright (c) 2017 Siro Díaz Palazón
7		* @license https://github.com/SiroDiaz/DataStructures/blob/master/README.md (MIT License)
8		*/
9		namespace DataStructures\Trees;
10
11		use DataStructures\Trees\BinaryTreeAbstract;
12		use DataStructures\Trees\Nodes\AVLNode;
13
14		/**
15		* AVLTree
16		*
17		* This class is an implementation of a AVL tree. It has as main feature that access,
18		* insertion and deletion is O(log n). This is like a BST but it has a slightly difference
19		* in nodes: contains a height attribute, used to detect when is needed to rebalance the
20		* tree to keep the O(log n).
21		*
22		* @author Siro Diaz Palazon <[email protected]>
23		*/
24		class AVLTree extends BinaryTreeAbstract {
25
26		/**
27		* Creates a AVLNode.
28		*
29		* @param int\|string $key the key used to store.
30		* @param mixed $data the data.
31		* @param DataStructures\Trees\Nodes\AVLNode\|null $parent the parent node.
32		* @param DataStructures\Trees\Nodes\AVLNode\|null $left the left child node.
33		* @param DataStructures\Trees\Nodes\AVLNode\|null $right the right child node.
34		*
35		* @return DataStructures\Trees\Nodes\AVLNode the new node created.
36		*/
37		public function createNode($key, $data, $parent = null, $left = null, $right = null) {
38		return new AVLNode($key, $data, $parent, $left, $right);
39		}
40
41		/**
42		* Does a right rotation.
43		* Example, rotate Y
44		* k2 k1
45		* / \ / \
46		* k1 Z ==> X k2
47		* / \ / \
48		*X Y Y Z
49		*
50		*/
51	View Code Duplication	private function rightRotation(AVLNode $node) {
		0 ignored issues – show Duplication introduced 2017-06-11 05:48 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
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
78		* / \ / \
79		* X k1 ==> k2 Z
80		* / \ / \
81		* Y Z X Y
82		*/
83	View Code Duplication	private function leftRotation(AVLNode $node) {
		0 ignored issues – show Duplication introduced 2017-06-11 05:48 UTC by Report Bug Copy Issue Report This method seems to be duplicated in your project. Duplicated code is one of the most pungent code smells. If you need to duplicate the same code in three or more different places, we strongly encourage you to look into extracting the code into a single class or operation. You can also find more detailed suggestions in the “Code” section of your repository. Loading history...
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
108		* that detects the imbalance and finally does a right rotation
109		* in the subtree root that detects the imbalance.
110		* Case Right-Left.
111		*/
112		private function doubleRightRotation(AVLNode $node) {
113		$this->leftRotation($node->right);
114		$this->rightRotation($node);
115		}
116
117		/**
118		* Double left rotation does first a right rotation of left child node
119		* that detects the imbalance and finally does a left rotation
120		* in the subtree root that detects the imbalance.
121		* Case Left-Right.
122		*/
123		private function doubleLeftRotation(AVLNode $node) {
124		$this->rightRotation($node->left);
125		$this->leftRotation($node);
126		}
127
128		public function put($key, $data, $update = false) {
129		$nodeInserted = parent::put($key, $data, $update);
		0 ignored issues – show Unused Code introduced 2017-06-27 11:14 UTC by Report Bug Copy Issue Report `$nodeInserted` is not used, you could remove the assignment. This check looks for variable assignements that are either overwritten by other assignments or where the variable is not used subsequently. $myVar = 'Value'; $higher = false; if (rand(1, 6) > 3) { $higher = true; } else { $higher = false; } Both the `$myVar` assignment in line 1 and the `$higher` assignment in line 2 are dead. The first because `$myVar` is never used and the second because `$higher` is always overwritten for every possible time line. Loading history...
130		}
131
132		private function adjustHeight(AVLNode $node) {
133		$node->height = 1 + max($node->left->height, $node->right->height);
134		}
135		}

SiroDiaz / DataStructures

Push — master ( 5d2724...f24b80 )

AVLTree::rightRotation() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like