AVLTree::put() - Code Metrics - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

AVLTree::put() A
last analyzed 2017-08-06 10:37 UTC

↳ Parent: AVLTree

Complexity

Conditions	1
Paths	1

Size

Total Lines	6
Code Lines	4

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
c	1
b	0
f	0
dl	0
loc	6
rs	9.4285
cc	1
eloc	4
nc	1
nop	3

<?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.
     * 
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function rightRotation(AVLNode &$node) {
        $temp = &$node->left;
        $temp->parent = &$node->parent;

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

        $temp->right = &$node;
        $node->parent = &$temp;

        // temp took over node's place so now its parent should point to temp
        if ($temp->parent !== null) {
            if ($node === $temp->parent->left) {
                $temp->parent->left = &$temp;
            } else {
                $temp->parent->right = &$temp;
            }
        } else {
            $this->root = &$temp;
        }
        
        return $temp;
    }

    /**
     * Does a right rotation.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function leftRotation(AVLNode &$node) {

        $temp = &$node->right;
        $temp->parent = &$node->parent;

        $node->right = &$temp->left;

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

        $temp->left = &$node;
        $node->parent = &$temp;

        // temp took over node's place so now its parent should point to temp
        if ($temp->parent !== null) {
            if ($node == $temp->parent->left) {
                $temp->parent->left = &$temp;
            } else {
                $temp->parent->right = &$temp;
            }
        } else {
            $this->root = &$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.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function doubleRightRotation(AVLNode &$node) {
        $this->leftRotation($node->left);
        return $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.
     *
     * @param DataStructures\Trees\Nodes\AVLNode $node The node to be
     * rotated.
     * @return DataStructures\Trees\Nodes\AVLNode
     */
    private function doubleLeftRotation(AVLNode &$node) {
        $this->rightRotation($node->right);
        return $this->leftRotation($node);
    }

    /**
     * {@inheritDoc}
     */
    public function put($key, $data, $update = false) {
        $nodeInserted = parent::put($key, $data, $update);
        $this->rebalance($nodeInserted);

        return $nodeInserted;
    }

    /**
     * {@inheritDoc}
     */
    public function delete($key) {
        $nodeDelete = $this->search($key);
        if($nodeDelete !== null) {
            $successorNode = parent::delete($key);
            if($successorNode !== null) {
                $minimumNode = ($successorNode->right !== null) ?
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                    $this->getMinNode($successorNode->right) : $successorNode;
interface SomeInterface { }
class SomeClass implements SomeInterface {
    public $a;
}

function someFunction(SomeInterface $object) {
    if ($object instanceof SomeClass) {
        $a = $object->a;
    }
}
                
                $this->recomputeHeight($minimumNode);
                $this->rebalance($minimumNode);
            } else {
                $this->recomputeHeight($nodeDelete->parent);
                $this->rebalance($nodeDelete->parent);
            }

            return $successorNode;
        }
        
        return null;
    }

    /**
     * Rebalance the tree if the difference of height is greater than 1
     * between the right and left subtree or reverse. Then it apply a rotation
     * depending on the type of unbalance.
     *
     * @param DataStructures\Trees\Nodes\AVLNode
     */
    private function rebalance(&$node) {
        while($node !== null) {
            $parent = &$node->parent;

            $leftHeight = ($node->left === null) ? 0 : $node->left->height;
            $rightHeight = ($node->right === null) ? 0 : $node->right->height;
            $nodeBalance = $rightHeight - $leftHeight;

            if($nodeBalance >= 2) {
                if($node->right->right !== null) {
                    $this->leftRotation($node);
                    return;
                } else {
                    $this->doubleLeftRotation($node);
                    return;
                }
            } else if($nodeBalance <= -2) {
                if($node->left->left !== null) {
                    $this->rightRotation($node);
                    return;
                } else {
                    $this->doubleRightRotation($node);
                    return;
                }
            } else {
                $this->adjustHeight($node);
            }

            $node = &$parent;
        }
    }

    /**
     * Recomputes the height of the nodes ascending in the tree.
     * 
     * @param DataStructures\Trees\Nodes\AVLNode
     */
    private function recomputeHeight($node) {
        while($node !== null) {
            $node->height = $this->maxHeight($node->left, $node->right) + 1;
            $node = &$node->parent;
        }
    }

    /**
     * Returns the maximum height between two subtrees.
     * 
     * @param DataStructures\Trees\Nodes\AVLNode|null
     * @param DataStructures\Trees\Nodes\AVLNode|null
     * @return int the maximum height
     */
    private function maxHeight($node1, $node2) {
        if($node1 !== null && $node2 !== null) {
            return $node1->height > $node2->height ? $node1->height : $node2->height;
        } else if($node1 === null) {
            return $node2 !== null ? $node2->height : 0;
        } else if($node2 === null) {
            return $node1 !== null ? $node1->height : 0;
        }

        return 0;
    }

    /**
     * Adjust the height of the node.
     * 
     * @param DataStructures\Trees\Nodes\AVLNode
     */
    private function adjustHeight(&$node) {
        $leftHeight = ($node->left === null) ? 0 : $node->left->height;
        $rightHeight = ($node->right === null) ? 0 : $node->right->height;
        
        $node->height = 1 + max($leftHeight, $rightHeight);
    }
}

AVLTree::put() A
last analyzed 2017-08-06 10:37 UTC

Complexity

Size

Duplication

Importance

Available Fixes

Available Fixes

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			*
44			* @param DataStructures\Trees\Nodes\AVLNode $node The node to be
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 = &$node;
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 {
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.
132			* @return DataStructures\Trees\Nodes\AVLNode
133			*/
134			private function doubleLeftRotation(AVLNode &$node) {
135			$this->rightRotation($node->right);
136			return $this->leftRotation($node);
137			}
138
139			/**
140			* {@inheritDoc}
141			*/
142			public function put($key, $data, $update = false) {
143			$nodeInserted = parent::put($key, $data, $update);
144			$this->rebalance($nodeInserted);
145
146			return $nodeInserted;
147			}
148
149			/**
150			* {@inheritDoc}
151			*/
152			public function delete($key) {
153			$nodeDelete = $this->search($key);
154			if($nodeDelete !== null) {
155			$successorNode = parent::delete($key);
156			if($successorNode !== null) {
157			$minimumNode = ($successorNode->right !== null) ?
			0 ignored issues – show Bug introduced 2017-06-29 10:39 UTC by Report Bug Copy Issue Report Accessing `right` on the interface `DataStructures\Trees\Int...ces\BinaryNodeInterface` suggest that you code against a concrete implementation. How about adding an `instanceof` check? If you access a property on an interface, you most likely code against a concrete implementation of the interface. Available Fixes Adding an additional type check: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeInterface $object) { if ($object instanceof SomeClass) { $a = $object->a; } } Changing the type hint: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeClass $object) { $a = $object->a; } Loading history...
158			$this->getMinNode($successorNode->right) : $successorNode;
			0 ignored issues – show Bug introduced 2017-06-29 10:39 UTC by Report Bug Copy Issue Report Accessing `right` on the interface `DataStructures\Trees\Int...ces\BinaryNodeInterface` suggest that you code against a concrete implementation. How about adding an `instanceof` check? If you access a property on an interface, you most likely code against a concrete implementation of the interface. Available Fixes Adding an additional type check: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeInterface $object) { if ($object instanceof SomeClass) { $a = $object->a; } } Changing the type hint: interface SomeInterface { } class SomeClass implements SomeInterface { public $a; } function someFunction(SomeClass $object) { $a = $object->a; } Loading history...
159
160			$this->recomputeHeight($minimumNode);
161			$this->rebalance($minimumNode);
162			} else {
163			$this->recomputeHeight($nodeDelete->parent);
164			$this->rebalance($nodeDelete->parent);
165			}
166
167			return $successorNode;
168			}
169
170			return null;
171			}
172
173			/**
174			* Rebalance the tree if the difference of height is greater than 1
175			* between the right and left subtree or reverse. Then it apply a rotation
176			* depending on the type of unbalance.
177			*
178			* @param DataStructures\Trees\Nodes\AVLNode
179			*/
180			private function rebalance(&$node) {
181			while($node !== null) {
182			$parent = &$node->parent;
183
184			$leftHeight = ($node->left === null) ? 0 : $node->left->height;
185			$rightHeight = ($node->right === null) ? 0 : $node->right->height;
186			$nodeBalance = $rightHeight - $leftHeight;
187
188			if($nodeBalance >= 2) {
189			if($node->right->right !== null) {
190			$this->leftRotation($node);
191			return;
192			} else {
193			$this->doubleLeftRotation($node);
194			return;
195			}
196			} else if($nodeBalance <= -2) {
197			if($node->left->left !== null) {
198			$this->rightRotation($node);
199			return;
200			} else {
201			$this->doubleRightRotation($node);
202			return;
203			}
204			} else {
205			$this->adjustHeight($node);
206			}
207
208			$node = &$parent;
209			}
210			}
211
212			/**
213			* Recomputes the height of the nodes ascending in the tree.
214			*
215			* @param DataStructures\Trees\Nodes\AVLNode
216			*/
217			private function recomputeHeight($node) {
218			while($node !== null) {
219			$node->height = $this->maxHeight($node->left, $node->right) + 1;
220			$node = &$node->parent;
221			}
222			}
223
224			/**
225			* Returns the maximum height between two subtrees.
226			*
227			* @param DataStructures\Trees\Nodes\AVLNode\|null
228			* @param DataStructures\Trees\Nodes\AVLNode\|null
229			* @return int the maximum height
230			*/
231			private function maxHeight($node1, $node2) {
232			if($node1 !== null && $node2 !== null) {
233			return $node1->height > $node2->height ? $node1->height : $node2->height;
234			} else if($node1 === null) {
235			return $node2 !== null ? $node2->height : 0;
236			} else if($node2 === null) {
237			return $node1 !== null ? $node1->height : 0;
238			}
239
240			return 0;
241			}
242
243			/**
244			* Adjust the height of the node.
245			*
246			* @param DataStructures\Trees\Nodes\AVLNode
247			*/
248			private function adjustHeight(&$node) {
249			$leftHeight = ($node->left === null) ? 0 : $node->left->height;
250			$rightHeight = ($node->right === null) ? 0 : $node->right->height;
251
252			$node->height = 1 + max($leftHeight, $rightHeight);
253			}
254			}

SiroDiaz / DataStructures

AVLTree::put() A last analyzed 2017-08-06 10:37 UTC

Complexity

Size

Duplication

Importance

Available Fixes

Available Fixes

Duplication Side-by-Side

Filter issues like

AVLTree::put() A
last analyzed 2017-08-06 10:37 UTC