| 83 | } |
| 84 | |
| 85 | func TestRBTree(t *testing.T) { |
| 86 | testcases := []int{100, 200, 1000, 10000} |
| 87 | for _, n := range testcases { |
| 88 | rnd := rand.New(rand.NewSource(time.Now().UnixNano())) |
| 89 | tree := bt.NewRB[int]() |
| 90 | nums := rnd.Perm(n) |
| 91 | tree.Push(nums...) |
| 92 | |
| 93 | rets := tree.InOrder() |
| 94 | if !sort.IntsAreSorted(rets) { |
| 95 | t.Error("Error with Push") |
| 96 | } |
| 97 | |
| 98 | if res, ok := tree.Min(); !ok || res != rets[0] { |
| 99 | t.Errorf("Error with Min, get %d, want: %d", res, rets[0]) |
| 100 | } |
| 101 | |
| 102 | if res, ok := tree.Max(); !ok || res != rets[n-1] { |
| 103 | t.Errorf("Error with Max, get %d, want: %d", res, rets[n-1]) |
| 104 | } |
| 105 | |
| 106 | for i := 0; i < n-1; i++ { |
| 107 | if ret, ok := tree.Successor(rets[0]); ret != rets[1] || !ok { |
| 108 | t.Error("Error with Successor") |
| 109 | } |
| 110 | if ret, ok := tree.Predecessor(rets[1]); ret != rets[0] || !ok { |
| 111 | t.Error("Error with Predecessor") |
| 112 | } |
| 113 | |
| 114 | ok := tree.Delete(nums[i]) |
| 115 | rets = tree.InOrder() |
| 116 | if !ok || !sort.IntsAreSorted(rets) { |
| 117 | t.Errorf("Error With Delete") |
| 118 | } |
| 119 | } |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | func TestRBTreeString(t *testing.T) { |
| 124 | tree := bt.NewRB[string]() |