AVLTree::delete() - Code Metrics - Inspection of "Rewrite rotations and implemented insertion in AVL..." - SiroDiaz/DataStructures - Measure and Improve Code Quality continuously with Scrutinizer

Completed

Push — master ( 75a093...5c8b24 )

by Siro Díaz

created 2017-06-27 23:27 UTC

AVLTree::delete() A

↳ Parent: AVLTree

Complexity

Conditions	1
Paths	1

Size

Total Lines	5
Code Lines	3

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
c	0
b	0
f	0
dl	0
loc	5
rs	9.4285
cc	1
eloc	3
nc	1
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;
        $temp->parent = &$node->parent;

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

        }

        $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;
        /*

        $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.
     */
    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;
        /*

        $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->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.
     */
    private function doubleLeftRotation(AVLNode &$node) {
        $this->leftRotation($node->right);
        return $this->rightRotation($node);
    }

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

        return $nodeInserted;
    }

    /**
     *
     */
    public function delete($key) {
        $nodeRemoved = parent::delete($key);

        return $nodeRemoved;
    }

    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;
        }
    }

    /**
     *
     */
    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);
    }
}

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		$temp->parent = &$node->parent;
54
55		$node->left = &$temp->right;
56		if ($node->left !== null) {
57		$node->left->parent = &$snode;
		0 ignored issues – show Bug introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report The variable `$snode` does not exist. Did you forget to declare it? This check marks access to variables or properties that have not been declared yet. While PHP has no explicit notion of declaring a variable, accessing it before a value is assigned to it is most likely a bug. Loading history...
58		}
59
60		$temp->right = &$node;
61		$node->parent = &$temp;
62
63		// temp took over node's place so now its parent should point to temp
64		if ($temp->parent !== null) {
65		if ($node === $temp->parent->left) {
66		$temp->parent->left = &$temp;
67		} else {
68		$temp->parent->right = &$temp;
69		}
70		} else {
71		$this->root = &$temp;
72		}
73
74		return $temp;
75		/*
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report `53%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
76		$temp = &$node->left;
77
78		if($node->parent !== null) {
79		if($node->parent->right !== null) {
80		$node->parent->right = &$temp;
81		} else {
82		$node->parent->left = &$temp;
83		}
84		}
85
86		$temp->parent = &$node->parent;
87		$node->parent = &$temp;
88		$node->left = $temp->right;
89		if($node->left !== null) {
90		$node->left->parent = &$node;
91		}
92		$temp->right = &$node;
93
94		$this->adjustHeight($node);
95		$this->adjustHeight($temp);
96
97		return $temp;
98		*/
99		}
100
101		/*
102		* Does a right rotation.
103		*/
104	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...
105
106		$temp = &$node->right;
107		$temp->parent = &$node->parent;
108
109		$node->right = &$temp->left;
110
111		if ($node->right !== null) {
112		$node->right->parent = &$node;
113		}
114
115		$temp->left = &$node;
116		$node->parent = &$temp;
117
118		// temp took over node's place so now its parent should point to temp
119		if ($temp->parent !== null) {
120		if ($node == $temp->parent->left) {
121		$temp->parent->left = &$temp;
122		} else {
123		$temp->parent->right = &$temp;
124		}
125		} else {
126		$this->root = &$temp;
127		}
128
129		return $temp;
130		/*
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report `52%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
131		$temp = &$node->right;
132		if($node->parent !== null) {
133		if($node->parent->right === $node) {
134		$node->parent->right = &$node;
135		} else {
136		$node->parent->left = &$node;
137		}
138		}
139		$temp->parent = &$node->parent;
140		$node->parent = &$temp;
141		$node->right = $temp->left;
142		if($node->right !== null) {
143		$node->right->parent = &$node;
144		}
145		$temp->left = &$node;
146		*/
147		// $this->adjustHeight($node);
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report `75%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
148		// $this->adjustHeight($temp);
		0 ignored issues – show Unused Code Comprehensibility introduced 2017-06-27 23:28 UTC by Report Bug Copy Issue Report `75%` of this comment could be valid code. Did you maybe forget this after debugging? Sometimes obsolete code just ends up commented out instead of removed. In this case it is better to remove the code once you have checked you do not need it. The code might also have been commented out for debugging purposes. In this case it is vital that someone uncomments it again or your project may behave in very unexpected ways in production. This check looks for comments that seem to be mostly valid code and reports them. Loading history...
149
150		// return $temp;
151		}
152
153		/**
154		* Double right rotation does first a left rotation of right child node
155		* that detects the imbalance and finally does a right rotation
156		* in the subtree root that detects the imbalance.
157		* Case Right-Left.
158		*/
159		private function doubleRightRotation(AVLNode &$node) {
160		$this->leftRotation($node->left);
161		return $this->rightRotation($node);
162		}
163
164		/**
165		* Double left rotation does first a right rotation of left child node
166		* that detects the imbalance and finally does a left rotation
167		* in the subtree root that detects the imbalance.
168		* Case Left-Right.
169		*/
170		private function doubleLeftRotation(AVLNode &$node) {
171		$this->leftRotation($node->right);
172		return $this->rightRotation($node);
173		}
174
175		/**
176		*
177		*/
178		public function put($key, $data, $update = false) {
179		$nodeInserted = parent::put($key, $data, $update);
180		$this->rebalance($nodeInserted);
181
182		return $nodeInserted;
183		}
184
185		/**
186		*
187		*/
188		public function delete($key) {
189		$nodeRemoved = parent::delete($key);
190
191		return $nodeRemoved;
192		}
193
194		private function rebalance(&$node) {
195		while($node !== null) {
196		$parent = &$node->parent;
197
198		$leftHeight = ($node->left === null) ? 0 : $node->left->height;
199		$rightHeight = ($node->right === null) ? 0 : $node->right->height;
200		$nodeBalance = $rightHeight - $leftHeight;
201
202		if($nodeBalance >= 2) {
203		if($node->right->right !== null) {
204		$this->leftRotation($node);
205		return;
206		} else {
207		$this->doubleLeftRotation($node);
208		return;
209		}
210		} else if($nodeBalance <= -2) {
211		if($node->left->left !== null) {
212		$this->rightRotation($node);
213		return;
214		} else {
215		$this->doubleRightRotation($node);
216		return;
217		}
218		} else {
219		$this->adjustHeight($node);
220		}
221
222		$node = &$parent;
223		}
224		}
225
226		/**
227		*
228		*/
229		private function adjustHeight(&$node) {
230		$leftHeight = ($node->left === null) ? 0 : $node->left->height;
231		$rightHeight = ($node->right === null) ? 0 : $node->right->height;
232
233		$node->height = 1 + max($leftHeight, $rightHeight);
234		}
235		}

SiroDiaz / DataStructures

Push — master ( 75a093...5c8b24 )

AVLTree::delete() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like