javascript-algorithms/test/data-structures/red-black-tree.spec.js at master · BIO2CS/javascript-algorithms · GitHub

Repository navigation

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

'use strict';

var mod = require('../../src/data-structures/red-black-tree.js');

var Vertex = mod.Node;

var RBTree = mod.RBTree;

var Colors = mod.Colors;

describe('Node', function () {

it('should be a constructor function', function () {

expect(typeof Vertex).toBe('function');

});

it('should set all properties via the constructor', function () {

var node = new Vertex('key', 'value', 1, 2, Colors.RED);

expect(node.getKey()).toBe('key');

expect(node.getLeft()).toBe(1);

expect(node.getRight()).toBe(2);

expect(node.getValue()).toBe('value');

expect(node.isRed()).toBeTruthy();

});

describe('Node flipColor', function () {

it('should has method flipColor', function () {

var node = new Vertex();

expect(typeof node.flipColor).toBe('function');

});

it('should work properly', function () {

var node = new Vertex();

expect(node.isRed()).toBe(false);

node.flipColor();

expect(node.isRed()).toBe(true);

node.flipColor();

expect(node.isRed()).toBe(false);

});

});

});

describe('RBTree', function () {

it('should be a constructor function', function () {

expect(typeof RBTree).toBe('function');

});

it('should initialize root to null by default', function () {

expect(new RBTree()._root).toBeNull();

});

describe('node insertion', function () {

it('should be able to insert a node in empty tree', function () {

var tree = new RBTree();

tree.put('foo', 'bar');

expect(tree._root.getKey()).toBe('foo');

expect(tree._root.getValue()).toBe('bar');

});

it('should be able to insert a node in 1 level tree', function () {

var tree = new RBTree();

tree.put(1, 'bar');

tree.put(0, 'baz');

expect(tree._root.getLeft()).not.toBeNull();

expect(tree._root.getLeft().isRed()).toBeTruthy();

tree.put(2, 'baz');

expect(tree._root.getRight()).not.toBeNull();

expect(tree._root.getRight().isRed()).toBeFalsy();

tree = new RBTree();

tree.put(1, 'bar');

tree.put(2, 'foo');

tree.put(3, 'baz');

expect(tree._root.getRight()).not.toBeNull();

expect(tree._root.getLeft()).not.toBeNull();

expect(tree._root.isRed()).toBeFalsy();

expect(tree._root.getRight().isRed()).toBeFalsy();

expect(tree._root.getLeft().isRed()).toBeFalsy();

tree.put(4, 'foobar');

tree.put(5, 'foobar');

expect(tree._root.getRight().getRight()).not.toBeNull();

expect(tree._root.getRight().getRight().isRed()).toBeFalsy();

});

});

describe('get method', function () {

it('should be able to find value by given key', function () {

var tree = new RBTree();

expect(tree.get(1)).toBeUndefined();

tree.put(1, 'baz');

expect(tree.get(1)).toBe('baz');

tree.put(2, 'foo');

expect(tree.get(2)).toBe('foo');

tree.put(3, 'bar');

expect(tree.get(3)).toBe('bar');

expect(tree.get(4)).toBeUndefined();

tree.put(5, 'foobar');

expect(tree.get(5)).toBe('foobar');

tree.put(5, 'foobar1');

expect(tree.get(5)).toBe('foobar1');

});

});

});