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

Commita133529

Browse files
authored
merge: Bugfix AVLTree comparator (#1084)
The original insertBalance function was doing raw value comparisons as opposed to using the tree's comparator. This is clearly unintentional, and would (ultimately) cause the structure to segfault when constructed with the stringData included in the updated test.I've added the fix, scanned the rest of the code for similar issues, and added the appropriate test case which passes successfully with the fix. The jest code coverage increases slightly as well with the changes.
1 parent9790468 commita133529

File tree

2 files changed

+17
-5
lines changed

2 files changed

+17
-5
lines changed

‎Data-Structures/Tree/AVLTree.js

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -90,14 +90,14 @@ const AVLTree = (function () {
9090
}
9191

9292
// check if tree is balanced else balance it for insertion
93-
constinsertBalance=function(node,_val,balanceFactor){
94-
if(balanceFactor>1&&_val<node._left._val){
93+
constinsertBalance=function(node,_val,balanceFactor,tree){
94+
if(balanceFactor>1&&tree._comp(_val,node._left._val)<0){
9595
returnrightRotate(node)// Left Left Case
9696
}
97-
if(balanceFactor<1&&_val>node._right._val){
97+
if(balanceFactor<1&&tree._comp(_val,node._right._val)>0){
9898
returnleftRotate(node)// Right Right Case
9999
}
100-
if(balanceFactor>1&&_val>node._left._val){
100+
if(balanceFactor>1&&tree._comp(_val,node._left._val)>0){
101101
node._left=leftRotate(node._left)// Left Right Case
102102
returnrightRotate(node)
103103
}
@@ -140,7 +140,7 @@ const AVLTree = (function () {
140140
}
141141
updateHeight(root)
142142
constbalanceFactor=getHeightDifference(root)
143-
returnisValidBalanceFactor(balanceFactor) ?root :insertBalance(root,val,balanceFactor)
143+
returnisValidBalanceFactor(balanceFactor) ?root :insertBalance(root,val,balanceFactor,tree)
144144
}
145145

146146
// delete am element

‎Data-Structures/Tree/test/AVLTree.test.js

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,26 +5,38 @@ describe('AVLTree Implementation: ', () => {
55
constdataList=[]
66
constdemoData=[1,4,6,22,7,99,4,66,77,98]
77

8+
constavlStringTree=newAVLTree()
9+
constcollator=newIntl.Collator()
10+
conststringData=['S','W','z','B','a']
11+
812
beforeAll(()=>{
913
demoData.forEach(item=>{
1014
if(avlTree.add(item)){
1115
dataList.push(item)
1216
}
1317
})
18+
19+
avlStringTree._comp=collator.compare
20+
stringData.forEach(item=>avlStringTree.add(item))
1421
})
1522

1623
it('checks if element is inserted properly',()=>{
1724
expect(dataList.length).toEqual(avlTree.size)
25+
expect(stringData.length).toEqual(avlStringTree.size)
1826
})
1927

2028
it('search if inserted element is present',()=>{
2129
demoData.forEach(data=>{
2230
expect(avlTree.find(data)).toBeTruthy()
2331
})
32+
stringData.forEach(data=>{
33+
expect(avlStringTree.find(data)).toBeTruthy()
34+
})
2435
})
2536

2637
it('deletes the inserted element',()=>{
2738
constdeleteElement=dataList[3]
2839
expect(avlTree.remove(deleteElement)).toBeTruthy()
40+
expect(avlStringTree.remove(stringData[3])).toBeTruthy()
2941
})
3042
})

0 commit comments

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