| 97 | |
| 98 | test.skip('random stress test', () => { |
| 99 | const assertAvl = (node: BinaryTreeNode<number> | null) => { |
| 100 | if (!node) return; |
| 101 | |
| 102 | // assert BST property |
| 103 | if (node.left) |
| 104 | expect(node.value).toBeGreaterThanOrEqual(node.left.value); |
| 105 | if (node.right) expect(node.value).toBeLessThan(node.right.value); |
| 106 | |
| 107 | // assert balancing property |
| 108 | const balance = |
| 109 | (node.left ? node.left!.height() + 1 : 0) - |
| 110 | (node.right ? node.right?.height() + 1 : 0); |
| 111 | expect(Math.abs(balance)).toBeLessThanOrEqual(1); |
| 112 | |
| 113 | assertAvl(node.left); |
| 114 | assertAvl(node.right); |
| 115 | }; |
| 116 | |
| 117 | const tree = new AVLTree(); |
| 118 | |