@@ -3,12 +3,14 @@ import { AVLTree } from '../AVLTree'
33describe ( 'AVLTree Implementation: ' , ( ) => {
44const avlTree = new AVLTree ( )
55const 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 ]
77
88const avlStringTree = new AVLTree ( )
99const collator = new Intl . Collator ( )
1010const stringData = [ 'S' , 'W' , 'z' , 'B' , 'a' ]
1111
12+ const emptyTree = new AVLTree ( collator . compare )
13+
1214beforeAll ( ( ) => {
1315demoData . forEach ( item => {
1416if ( avlTree . add ( item ) ) {
@@ -20,6 +22,11 @@ describe('AVLTree Implementation: ', () => {
2022stringData . forEach ( item => avlStringTree . add ( item ) )
2123} )
2224
25+ it ( 'delete and search from empty tree' , ( ) => {
26+ expect ( emptyTree . remove ( 0 ) ) . toBeFalsy ( )
27+ expect ( emptyTree . find ( 0 ) ) . toBeFalsy ( )
28+ } )
29+
2330it ( 'checks if element is inserted properly' , ( ) => {
2431expect ( dataList . length ) . toEqual ( avlTree . size )
2532expect ( stringData . length ) . toEqual ( avlStringTree . size )
@@ -34,9 +41,31 @@ describe('AVLTree Implementation: ', () => {
3441} )
3542} )
3643
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 ( )
4170} )
4271} )