forked from loiane/javascript-datastructures-algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathred-black-tree.spec.ts
113 lines (96 loc) · 3.75 KB
/
red-black-tree.spec.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import { Colors } from './../../../src/ts/data-structures/models/red-black-node';
import 'mocha';
import { expect } from 'chai';
import { RedBlackTree } from '../../../src/ts/index';
import { RedBlackNode } from '../../../src/ts/data-structures/models/red-black-node';
describe('RedBlackTree', () => {
let tree: RedBlackTree<number>;
beforeEach(() => {
tree = new RedBlackTree<number>();
});
it('starts empty', () => {
expect(tree.getRoot()).to.equal(undefined);
});
it('inserts elements in the RedBlackTree', () => {
expect(tree.getRoot()).to.equal(undefined);
let node;
tree.insert(1);
assertNode(tree.getRoot(), 1, Colors.BLACK);
tree.insert(2);
assertNode(tree.getRoot(), 1, Colors.BLACK);
assertNode(tree.getRoot().right, 2, Colors.RED);
tree.insert(3);
assertNode(tree.getRoot(), 2, Colors.BLACK);
assertNode(tree.getRoot().right, 3, Colors.RED);
assertNode(tree.getRoot().left, 1, Colors.RED);
tree.insert(4);
assertNode(tree.getRoot(), 2, Colors.BLACK);
assertNode(tree.getRoot().left, 1, Colors.BLACK);
assertNode(tree.getRoot().right, 3, Colors.BLACK);
assertNode(tree.getRoot().right.right, 4, Colors.RED);
tree.insert(5);
assertNode(tree.getRoot(), 2, Colors.BLACK);
assertNode(tree.getRoot().left, 1, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 4, Colors.BLACK);
assertNode(node.left, 3, Colors.RED);
assertNode(node.right, 5, Colors.RED);
tree.insert(6);
assertNode(tree.getRoot(), 2, Colors.BLACK);
assertNode(tree.getRoot().left, 1, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 4, Colors.RED);
assertNode(node.left, 3, Colors.BLACK);
assertNode(node.right, 5, Colors.BLACK);
assertNode(node.right.right, 6, Colors.RED);
tree.insert(7);
assertNode(tree.getRoot(), 2, Colors.BLACK);
assertNode(tree.getRoot().left, 1, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 4, Colors.RED);
assertNode(node.left, 3, Colors.BLACK);
assertNode(node.right, 6, Colors.BLACK);
assertNode(node.right.right, 7, Colors.RED);
assertNode(node.right.left, 5, Colors.RED);
tree.insert(8);
assertNode(tree.getRoot(), 4, Colors.BLACK);
node = tree.getRoot().left;
assertNode(node, 2, Colors.RED);
assertNode(node.left, 1, Colors.BLACK);
assertNode(node.right, 3, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 6, Colors.RED);
assertNode(node.left, 5, Colors.BLACK);
assertNode(node.right, 7, Colors.BLACK);
assertNode(node.right.right, 8, Colors.RED);
tree.insert(9);
assertNode(tree.getRoot(), 4, Colors.BLACK);
node = tree.getRoot().left;
assertNode(node, 2, Colors.RED);
assertNode(node.left, 1, Colors.BLACK);
assertNode(node.right, 3, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 6, Colors.RED);
assertNode(node.left, 5, Colors.BLACK);
assertNode(node.right, 8, Colors.BLACK);
assertNode(node.right.left, 7, Colors.RED);
assertNode(node.right.right, 9, Colors.RED);
tree.insert(10);
assertNode(tree.getRoot(), 4, Colors.BLACK);
node = tree.getRoot().left;
assertNode(node, 2, Colors.BLACK);
assertNode(node.left, 1, Colors.BLACK);
assertNode(node.right, 3, Colors.BLACK);
node = tree.getRoot().right;
assertNode(node, 6, Colors.BLACK);
assertNode(node.left, 5, Colors.BLACK);
assertNode(node.right, 8, Colors.RED);
assertNode(node.right.left, 7, Colors.BLACK);
assertNode(node.right.right, 9, Colors.BLACK);
assertNode(node.right.right.right, 10, Colors.RED);
});
function assertNode(node: RedBlackNode<number>, key: number, color: Colors) {
expect(node.color).to.equal(color);
expect(node.key).to.equal(key);
}
});