Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitafa4948

Browse files
committed
Simplify AVL tree node deletion.
1 parent04e533e commitafa4948

File tree

2 files changed

+72
-87
lines changed

2 files changed

+72
-87
lines changed

‎src/data-structures/tree/avl-tree/AvlTree.js

Lines changed: 5 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -16,54 +16,16 @@ export default class AvlTree extends BinarySearchTree {
1616
}
1717
}
1818

19-
remove(value){
20-
constnodeToRemove=this.root.find(value);
21-
22-
if(!nodeToRemove){
23-
thrownewError('Item not found in the tree');
24-
}
25-
26-
// Recursively find target node, if found then delete and balance.
27-
// return nodeToRemove.value;
28-
this.root=this.removeRecv(this.root,nodeToRemove);
29-
}
30-
31-
removeRecv(origin,node){
32-
letnewOrigin=origin;
33-
if(origin.value>node.value){
34-
// Recursively traversing from left
35-
newOrigin.left=this.removeRecv(origin.left,node);
36-
}elseif(origin.value<node.value){
37-
// Recursively traversing from right
38-
newOrigin.right=this.removeRecv(origin.right,node);
39-
}else{
40-
if(origin.left==null){
41-
// Forget right node
42-
returnorigin.right;
43-
}
44-
if(origin.right==null){
45-
// Forget left node
46-
returnorigin.left;
47-
}
48-
49-
// Recursively find min node from left subtree
50-
// more efficient traversing
51-
constparent=Object.assign({},origin);
52-
newOrigin=parent.right.findMin();
53-
newOrigin.right=this.deleteMin(parent.right);
54-
newOrigin.left=parent.left;
55-
}
56-
57-
// Balance and return root node
58-
returnthis.balance(newOrigin);
59-
}
60-
6119
/**
6220
*@param {*} value
6321
*@return {boolean}
6422
*/
6523
remove(value){
66-
thrownewError(`Can't remove${value}. Remove method is not implemented yet`);
24+
// Do standard BST removal.
25+
super.remove(value);
26+
27+
// Balance the tree starting from the root node.
28+
this.balance(this.root);
6729
}
6830

6931
/**
@@ -90,8 +52,6 @@ export default class AvlTree extends BinarySearchTree {
9052
this.rotateRightLeft(node);
9153
}
9254
}
93-
// Return the heap to avoid referenceError
94-
returnnode;
9555
}
9656

9757
/**
@@ -200,15 +160,4 @@ export default class AvlTree extends BinarySearchTree {
200160
// Attach rootNode to the left of rightNode.
201161
rightNode.setLeft(rootNode);
202162
}
203-
204-
deleteMin(node){
205-
// Forget right node if has value
206-
if(node.left==null)returnnode.right;
207-
208-
constnewNode=node;
209-
newNode.left=this.deleteMin(node.left);
210-
211-
// Balance and return root node
212-
returnthis.balance(newNode);
213-
}
214163
}

‎src/data-structures/tree/avl-tree/__test__/AvlTRee.test.js

Lines changed: 67 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -186,31 +186,6 @@ describe('AvlTree', () => {
186186
expect(tree.toString()).toBe('6,8,9,18,21,22,43');
187187
});
188188

189-
it('should keep balance after removal',()=>{
190-
consttree=newAvlTree();
191-
192-
tree.insert(1);
193-
tree.insert(2);
194-
tree.insert(3);
195-
tree.insert(4);
196-
tree.insert(5);
197-
tree.insert(6);
198-
tree.insert(7);
199-
tree.insert(8);
200-
tree.insert(9);
201-
202-
expect(tree.toString()).toBe('1,2,3,4,5,6,7,8,9');
203-
expect(tree.root.height).toBe(3);
204-
205-
tree.remove(8);
206-
tree.remove(9);
207-
208-
expect(tree.contains(8)).toBeFalsy();
209-
expect(tree.contains(9)).toBeFalsy();
210-
expect(tree.toString()).toBe('1,2,3,4,5,6,7');
211-
expect(tree.root.height).toBe(2);
212-
});
213-
214189
it('should do left right rotation and keeping left right node safe',()=>{
215190
consttree=newAvlTree();
216191

@@ -255,13 +230,74 @@ describe('AvlTree', () => {
255230
expect(tree.root.height).toBe(3);
256231
});
257232

258-
it('should throw an error when trying to remove the node',()=>{
259-
constremoveNodeAvlTree=()=>{
260-
consttree=newAvlTree();
233+
it('should remove values from the tree with right-right rotation',()=>{
234+
consttree=newAvlTree();
235+
236+
tree.insert(10);
237+
tree.insert(20);
238+
tree.insert(30);
239+
tree.insert(40);
240+
241+
expect(tree.toString()).toBe('10,20,30,40');
242+
243+
tree.remove(10);
244+
245+
expect(tree.toString()).toBe('20,30,40');
246+
expect(tree.root.value).toBe(30);
247+
expect(tree.root.left.value).toBe(20);
248+
expect(tree.root.right.value).toBe(40);
249+
expect(tree.root.balanceFactor).toBe(0);
250+
});
251+
252+
it('should remove values from the tree with left-left rotation',()=>{
253+
consttree=newAvlTree();
254+
255+
tree.insert(10);
256+
tree.insert(20);
257+
tree.insert(30);
258+
tree.insert(5);
259+
260+
expect(tree.toString()).toBe('5,10,20,30');
261+
262+
tree.remove(30);
263+
264+
expect(tree.toString()).toBe('5,10,20');
265+
expect(tree.root.value).toBe(10);
266+
expect(tree.root.left.value).toBe(5);
267+
expect(tree.root.right.value).toBe(20);
268+
expect(tree.root.balanceFactor).toBe(0);
269+
});
270+
271+
it('should keep balance after removal',()=>{
272+
consttree=newAvlTree();
273+
274+
tree.insert(1);
275+
tree.insert(2);
276+
tree.insert(3);
277+
tree.insert(4);
278+
tree.insert(5);
279+
tree.insert(6);
280+
tree.insert(7);
281+
tree.insert(8);
282+
tree.insert(9);
283+
284+
expect(tree.toString()).toBe('1,2,3,4,5,6,7,8,9');
285+
expect(tree.root.value).toBe(4);
286+
expect(tree.root.height).toBe(3);
287+
expect(tree.root.balanceFactor).toBe(-1);
288+
289+
tree.remove(8);
261290

262-
tree.remove(1);
263-
};
291+
expect(tree.root.value).toBe(4);
292+
expect(tree.root.balanceFactor).toBe(-1);
293+
294+
tree.remove(9);
264295

265-
expect(removeNodeAvlTree).toThrowError();
296+
expect(tree.contains(8)).toBeFalsy();
297+
expect(tree.contains(9)).toBeFalsy();
298+
expect(tree.toString()).toBe('1,2,3,4,5,6,7');
299+
expect(tree.root.value).toBe(4);
300+
expect(tree.root.height).toBe(2);
301+
expect(tree.root.balanceFactor).toBe(0);
266302
});
267303
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp