@@ -3,12 +3,14 @@ import { AVLTree } from '../AVLTree' |
3 | 3 | describe('AVLTree Implementation: ', () => { |
4 | 4 | const avlTree = new AVLTree() |
5 | 5 | const dataList = [] |
6 | | - const demoData = [1, 4, 6, 22, 7, 99, 4, 66, 77, 98] |
| 6 | + const demoData = [1, 4, 6, 22, 7, 99, 4, 66, 77, 98, 87, 54, 32, 15] |
7 | 7 |
|
8 | 8 | const avlStringTree = new AVLTree() |
9 | 9 | const collator = new Intl.Collator() |
10 | 10 | const stringData = ['S', 'W', 'z', 'B', 'a'] |
11 | 11 |
|
| 12 | + const emptyTree = new AVLTree(collator.compare) |
| 13 | + |
12 | 14 | beforeAll(() => { |
13 | 15 | demoData.forEach(item => { |
14 | 16 | if (avlTree.add(item)) { |
@@ -20,6 +22,11 @@ describe('AVLTree Implementation: ', () => { |
20 | 22 | stringData.forEach(item => avlStringTree.add(item)) |
21 | 23 | }) |
22 | 24 |
|
| 25 | + it('delete and search from empty tree', () => { |
| 26 | + expect(emptyTree.remove(0)).toBeFalsy() |
| 27 | + expect(emptyTree.find(0)).toBeFalsy() |
| 28 | + }) |
| 29 | + |
23 | 30 | it('checks if element is inserted properly', () => { |
24 | 31 | expect(dataList.length).toEqual(avlTree.size) |
25 | 32 | expect(stringData.length).toEqual(avlStringTree.size) |
@@ -34,9 +41,31 @@ describe('AVLTree Implementation: ', () => { |
34 | 41 | }) |
35 | 42 | }) |
36 | 43 |
|
37 | | - it('deletes the inserted element', () => { |
38 | | - const deleteElement = dataList[3] |
39 | | - expect(avlTree.remove(deleteElement)).toBeTruthy() |
40 | | - expect(avlStringTree.remove(stringData[3])).toBeTruthy() |
| 44 | + it('delete element with two valid children', () => { |
| 45 | + expect(avlTree.remove(77)).toBeTruthy() |
| 46 | + }) |
| 47 | + |
| 48 | + it('delete element missing L-child', () => { |
| 49 | + expect(avlTree.remove(98)).toBeTruthy() |
| 50 | + }) |
| 51 | + |
| 52 | + it('delete elements forcing single R-rotation', () => { |
| 53 | + expect(avlTree.remove(99)).toBeTruthy() |
| 54 | + expect(avlTree.remove(87)).toBeTruthy() |
| 55 | + }) |
| 56 | + |
| 57 | + it('delete elements forcing R-rotation and L-rotation', () => { |
| 58 | + expect(avlTree.remove(1)).toBeTruthy() |
| 59 | + expect(avlTree.remove(4)).toBeTruthy() |
| 60 | + }) |
| 61 | + |
| 62 | + it('delete elements forcing single L-rotation', () => { |
| 63 | + expect(avlTree.remove(7)).toBeTruthy() |
| 64 | + expect(avlTree.remove(15)).toBeTruthy() |
| 65 | + expect(avlTree.remove(6)).toBeTruthy() |
| 66 | + }) |
| 67 | + |
| 68 | + it('delete element forcing single L-rotation and R-rotation', () => { |
| 69 | + expect(avlTree.remove(66)).toBeTruthy() |
41 | 70 | }) |
42 | 71 | }) |