Skip to content

feat: AVLTree 100% test coverage #1098

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Sep 13, 2022
Merged

feat: AVLTree 100% test coverage #1098

Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
ed5db20
Bugfix AVLTree comparator
kho-kho-kho Aug 15, 2022
8ebb542
Merge branch 'TheAlgorithms:master' into master
kho-kho-kho Sep 12, 2022
2ea10b0
100% jest code coverage
kho-kho-kho Sep 13, 2022
5f3b57c
standard style fix
kho-kho-kho Sep 13, 2022
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
39 changes: 34 additions & 5 deletions Data-Structures/Tree/test/AVLTree.test.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -3,12 +3,14 @@ import { AVLTree } from '../AVLTree'
describe('AVLTree Implementation: ', () => {
const avlTree = new AVLTree()
const dataList = []
const demoData = [1, 4, 6, 22, 7, 99, 4, 66, 77, 98]
const demoData = [1, 4, 6, 22, 7, 99, 4, 66, 77, 98, 87, 54, 32, 15]

const avlStringTree = new AVLTree()
const collator = new Intl.Collator()
const stringData = ['S', 'W', 'z', 'B', 'a']

const emptyTree = new AVLTree(collator.compare)

beforeAll(() => {
demoData.forEach(item => {
if (avlTree.add(item)) {
Expand All @@ -20,6 +22,11 @@ describe('AVLTree Implementation: ', () => {
stringData.forEach(item => avlStringTree.add(item))
})

it('delete and search from empty tree', () => {
expect(emptyTree.remove(0)).toBeFalsy()
expect(emptyTree.find(0)).toBeFalsy()
})

it('checks if element is inserted properly', () => {
expect(dataList.length).toEqual(avlTree.size)
expect(stringData.length).toEqual(avlStringTree.size)
Expand All @@ -34,9 +41,31 @@ describe('AVLTree Implementation: ', () => {
})
})

it('deletes the inserted element', () => {
const deleteElement = dataList[3]
expect(avlTree.remove(deleteElement)).toBeTruthy()
expect(avlStringTree.remove(stringData[3])).toBeTruthy()
it('delete element with two valid children', () => {
expect(avlTree.remove(77)).toBeTruthy()
})

it('delete element missing L-child', () => {
expect(avlTree.remove(98)).toBeTruthy()
})

it('delete elements forcing single R-rotation', () => {
expect(avlTree.remove(99)).toBeTruthy()
expect(avlTree.remove(87)).toBeTruthy()
})

it('delete elements forcing R-rotation and L-rotation', () => {
expect(avlTree.remove(1)).toBeTruthy()
expect(avlTree.remove(4)).toBeTruthy()
})

it('delete elements forcing single L-rotation', () => {
expect(avlTree.remove(7)).toBeTruthy()
expect(avlTree.remove(15)).toBeTruthy()
expect(avlTree.remove(6)).toBeTruthy()
})

it('delete element forcing single L-rotation and R-rotation', () => {
expect(avlTree.remove(66)).toBeTruthy()
})
})