ds-in-cpp/TreeTest.cc at main · sudonam/ds-in-cpp · GitHub

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
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

#include "TreeAVL.hh"
#include "TreeAVLX.hh"

template <class K, class V>
bool isIsomorphic(typename AVLTree<K, V>::Node *x,
                  typename AVLTreeX<K, V>::Node *y) {
  if (x == nullptr && y == nullptr) return true;
  if (!x || !y) return false;
  if (x->height != y->height) return false;
  if (x->key != y->key) return false;
  return isIsomorphic<K, V>(x->left, y->left) &&
         isIsomorphic<K, V>(x->right, y->right);
}

int main() {
  std::mt19937 mt(std::random_device{}());
  std::uniform_int_distribution rand(10, 99);

  for (int i = 0; i < 512; i++) {
    std::cout << i + 1 << '\n';

    std::vector<int> a(1024);
    for (auto &e : a) e = rand(mt);

    AVLTree<int, int> recur;
    AVLTreeX<int, int> iter;

    assert(recur.root == nullptr);
    assert(iter.root == nullptr);

    for (auto &e : a) {
      recur.insert(e, e);
      assert(recur.isHeightConsistent());
      assert(recur.isAVL(0x80000000, 0x7fffffff));

      iter.insert(e, e);
      assert(recur.isHeightConsistent());
      assert(iter.isAVL(0x80000000, 0x7fffffff));

      assert((isIsomorphic<int, int>(recur.root, iter.root)));
    }

    for (const auto &e : a) {
      recur.remove(e);
      assert(recur.isHeightConsistent());
      assert(recur.isAVL(0x80000000, 0x7fffffff));

      if (iter.search(e)) iter.remove(e);
      assert(recur.isHeightConsistent());
      assert(recur.isAVL(0x80000000, 0x7fffffff));

      assert((isIsomorphic<int, int>(recur.root, iter.root)));
    }

    assert(recur.root == nullptr);
    assert(iter.root == nullptr);
  }
}