データ構造編①
ソート編①

問題文の横にある矢印をクリックすると答えが表示されます。

データ構造編

Q1 「配列とリストの違いを述べよ」

配列はあらかじめ連続した領域に要素を格納し、列の何番目かを指定すると、O(1)でその位置の要素を取得できるのに対し、リストは要素一つ一つに独立した領域を確保しておき、次の要素を格納したポインタを前の要素に持たさせておため、i番目の要素を取り出すには、一番前の要素から順にたどっていく必要があり、O(n)かかる。逆に要素の挿入・削除の際には、変更箇所以降または以前の要素をずらす必要がある配列はO(n)かかるのに対し、リストでは変更箇所のポインタを付け替えるだけでよくO(1)ですむ。よって、列の長さが変わることがあまりなく要素へのランダムアクセスが頻繁であるときは配列を使うのが適切だが、列の要素が挿入や削除などの長さが変わる操作が頻繁に起こる時はリストの方が適切である。

Q2 「スタックの動作を説明せよ」

スタックは、後入れ先出しであり、最後に挿入された要素が最初に出る。

Q3 「スタックを実装せよ」

#include <iostream>
#include <vector>

template <typename T> struct Stack {
  std::vector<T> data;
  int size = 0;
  Stack(){};

  T top() { return data[size - 1]; }
  void pop() {
    size--;
    data.erase(data.begin() + size - 1);
  }
  void push(T element) {
    size++;
    data.push_back(element);
  }
};

int main() {
  Stack<int> stack;
  stack.push(1);
  std::cout << stack.top() << std::endl;
  stack.push(2);
  std::cout << stack.top() << std::endl;
  stack.pop();
  std::cout << stack.top() << std::endl;
}

Q4 「キューの動作を説明せよ」

キューは、後入れ先出しであり、最初に挿入されたものから出ていく

Q5 「キューを循環配列を用いて実装せよ」

#include <iostream>
#include <vector>

template <typename T> struct Queue {
  std::vector<T> data;
  int max_size;
  int size = 0;
  int front_idx = 0;
  int rear_idx = -1;
  Queue(int max_size_) {
    max_size = max_size_;
    data.resize(max_size);
  };

  T top() { return data[front_idx]; };
  bool empty() { return size == 0; }
  bool full() { return size == max_size; }
  void pop() {
    size--;
    front_idx = (front_idx + 1) % max_size;
  }
  void push(T element) {
    if (!full()) {
      size++;
      rear_idx = (rear_idx + 1) % max_size;
      data[rear_idx] = element;
    }
  }
};

int main() {
  Queue<int> que(5);
  std::cout << "Empty: " << que.empty() << std::endl;
  que.push(1);
  std::cout << que.top() << std::endl;
  que.push(2);
  std::cout << que.top() << std::endl;
  que.push(3);
  que.pop();
  std::cout << que.top() << std::endl;
  que.push(4);
  que.push(5);
  std::cout << "Full: " << que.full() << std::endl;
  que.push(6);
  std::cout << "Full: " << que.full() << std::endl;
  que.pop();
  std::cout << que.top() << std::endl;
  que.pop();
  std::cout << que.top() << std::endl;
  que.pop();
  std::cout << que.top() << std::endl;
  que.pop();
  std::cout << "Empty: " << que.empty() << std::endl;
  std::cout << que.top() << std::endl;
  que.pop();
  std::cout << "Empty: " << que.empty() << std::endl;
  que.push(7);
  std::cout << "Empty: " << que.empty() << std::endl;
  std::cout << que.top() << std::endl;
}

Q6 「ヒープの動作を説明せよ」

ヒープでは、要素に優先度がついており、挿入された順番にかかわらず、優先度の高いものから順に取り出される。

Q7 「ヒープを実装せよ」

#include <iostream>
#include <vector>

template <typename T> struct Heap {
  int size = 0;
  std::vector<T> data;

  Heap(){};

  T top() { return data[0]; }

  bool empty() { return size == 0; }

  void pop() {
    data[0] = data[size - 1];
    size--;
    int cur = 0;
    T tmp_1, tmp_2;
    while (cur < size) {
      if (data[cur] < data[cur * 2 + 1]) {
        if (data[cur * 2 + 1] > data[cur * 2 + 2]) {
          tmp_1 = data[cur];
          tmp_2 = data[cur * 2 + 1];
          data[cur] = tmp_2;
          data[cur * 2 + 1] = tmp_1;
          cur = cur * 2 + 1;
        } else {
          tmp_1 = data[cur];
          tmp_2 = data[cur * 2 + 2];
          data[cur] = tmp_2;
          data[cur * 2 + 2] = tmp_1;
          cur = cur * 2 + 2;
        }
      } else if (data[cur] < data[cur * 2 + 2]) {
        tmp_1 = data[cur];
        tmp_2 = data[cur * 2 + 2];
        data[cur] = tmp_2;
        data[cur * 2 + 2] = tmp_1;
        cur = cur * 2 + 2;
      } else {
        break;
      }
    }
    data.resize(size);
  }

  void push(T element) {
    data.push_back(element);
    size++;
    int cur = size - 1;
    T tmp_1, tmp_2;
    while (cur > 0) {
      if (data[cur] > data[(cur - 1) / 2]) {
        tmp_1 = data[cur];
        tmp_2 = data[(cur - 1) / 2];
        data[cur] = tmp_2;
        data[(cur - 1) / 2] = tmp_1;
        cur = (cur - 1) / 2;
      } else {
        break;
      }
    }
  }
};

int main() {
  Heap<int> heap;
  std::cout << "Push 1" << std::endl;
  heap.push(1);
  std::cout << heap.top() << std::endl;
  std::cout << "Push 5" << std::endl;
  heap.push(5);
  std::cout << heap.top() << std::endl;
  std::cout << "Push 3" << std::endl;
  heap.push(3);
  std::cout << heap.top() << std::endl;
  std::cout << "Pop" << std::endl;
  heap.pop();
  std::cout << heap.top() << std::endl;
  std::cout << "Push 17" << std::endl;
  heap.push(17);
  std::cout << heap.top() << std::endl;
  std::cout << "Push 8" << std::endl;
  heap.push(8);
  std::cout << heap.top() << std::endl;
  std::cout << "Push 43" << std::endl;
  heap.push(43);
  std::cout << heap.top() << std::endl;
}

Q8 「ヒープの要素追加および最小要素取り出しにかかる計算量を求めよ」

ヒープにおける要素追加および最小要素取り出しにかかる作業の回数は木の高さを超えることがない。要素数を$n$とすると、木の高さ $k$ は $2^{k-1} \leq n$ を満たすので、計算量は $O(log_{2}n)$ となる。

Q9 「2分探索木を実装せよ」

#include <iostream>
#include <vector>

template <typename T> struct Node {
  T val;
  Node *left;
  Node *right;

  Node(T val_) { val = val_; }
};

// WIP
template <typename T> Node<T> *delete_and_reshape(Node<T> *node, T element) {
  if (node == nullptr) {
    return node;
  }
}

template <typename T> struct BinaryTree {
  int size = 0;
  Node<T> *root;

  T min() {
    Node<T> *cur = root;
    while (true) {
      if (cur->left == nullptr) {
        return cur->val;
      } else {
        cur = cur->left;
      }
    }
  }

  Node<T> *find(T element) {
    Node<T> *cur = root;
    while (cur != nullptr) {
      if (element == cur->val) {
        return cur;
      } else if (element < cur->val) {
        cur = cur->left;
      } else {
        cur = cur->right;
      }
    }
    return nullptr;
  }

  void push(T element) {
    Node<T> *cur = root;
    while (true) {
      if (cur == nullptr) {
        cur = new Node<T>(element);
        break;
      } else if (element < cur->val) {
        cur = cur->left;
      } else {
        cur = cur->right;
      }
    }
  }

  void erase(T element) {}
};

Q10 「2分探索木の要素取り出しにかかる最悪および平均計算量を求め、ヒープと比較せよ」

全ての要素が片方向に偏っている場合は明らかに $O(n)$ かかる。また、n個の異なる要素を挿入した時の木の深さの期待値をT(n)とすると、左の木の要素数を $i$ 個とおいた時、

\begin{align}
T(n) &= \frac{1}{n} \sum_{i=0}^{n-1} \frac{1}{n} + \frac{i (T(i) + 1)}{n} + \frac{(n - i - 1) (T(n - i - 1) + 1)}{n} \\
     &= 1 + \frac{2}{n^2} \sum_{i=0}^{n-1} iT(i)
\end{align}

ここで、数学的帰納法を用いて $T(n) \leq a\log{n} + b$ (a, bはある実数)を示す。まず明らかに、$T(0) = 0$, $T(1) = 1$ であり、b=1の時に成立する。ここである2以上の自然数$k$に対して $T(n) \leq a\log{n} + 1 \quad (\forall n < k)$ と仮定すると、

\begin{align}
T(k) &= 1 + \frac{2}{k^{2}} \sum_{i=1}^{k-1} i T(i) \\
     &\leq 1 + \frac{2}{k^{2}} \sum_{i=1}^{k-1} (ai\log{i} + i) \\
     &\leq 2 + \frac{2a}{k^{2}} \sum_{i=1}^{k-1} i\log{i} \\
     & < 2 +  \frac{2a}{k^{2}} (\sum_{i=1}^{k/2} i\log{\frac{k}{2}} + \sum_{i=\frac{k}{2} + 1}^{k-1} i \log{k}) \\
     &\leq 2 + \frac{2a}{k^{2}} \{\frac{k^{2}}{8}(\log{k} - 1) + \frac{3k^{2}}{8} \log{k} \}  \\
     &= 2 - \frac{a}{4} + a\log{k} \\
     &\leq 1 + a\log{k}
\end{align}

よって、ヒープでは最小要素の取り出し以外にはO(n)かかるのに対し、二分探索木ではどの要素も平均$O(logn)$で取り出すことができる。

Q11 「2分探索木に対する平衡木の利点を述べよ」

2分探索木は最悪の場合でO(n)かかるが、平衡木は木の構造が変わるたびにバランスをとることで、最悪計算量を抑えることができる。

Q12 「2-3木を実装せよ」

#include <iostream>
using namespace std;

// based on http://www.nct9.ne.jp/m_hiroi/light/pyalgo14.html

// 二部探索木は、挿入や削除の順番によってバランスが崩れ、最悪O(nの計算量がかかることがある
// 最悪計算量を抑えるためには、木の構造が変わるたびにバランスを取ればよい
// このような木のことを平衡木と呼ぶ
// ここでは、2-3木を実装する
// 要素はすべて葉に格納する, 途中のノードはすべてインデックスとして機能する
// 途中ノードはすべて2つか3つの子ノードを持ち、2番目および3番目の子の子孫の最小値をインデックス情報として格納する

// 全ての要素は非負と仮定する
struct Node {
  int data1 = -1;
  int data2 = -1;
  Node *left;
  Node *mid;
  Node *right;

  Node(int data, Node *left_, Node *mid_) {
    data1 = data;
    left = left_;
    mid = mid_;
  }
};

pair<Node *, int> insert_leaf(Node *node, int x) {}

// 部分木nodeにデータxを挿入し、節を分割した場合には、新しい値と中央値を返す
pair<Node *, int> insert_node(Node *node, int x) {
  if (node->data1 == x || node->data2 == x) {
    return make_pair(nullptr, -1);
  }

  if (node->left == nullptr) {
    return insert_leaf(node, x);
  }

  if (x < node->data1) {
    pair<Node *, int> temp = insert_node(node->left, x);
    Node *new_node = temp.first;
    int mid_data = temp.second;

    if (new_node == nullptr) {
      return make_pair(nullptr, -1);
    }

    if (node->right != nullptr) {
      // split
      // 元のmidとrightを子にもつ新しいnew_node1を作成
      Node *new_node1 = new Node(node->data2, node->mid, node->right);
      // 元のmidにはnew_nodeを挿入する
      node->mid = new_node;
      node->right = nullptr;
      int mid_data1 = node->data1;
      node->data1 = mid_data;
      node->data2 = -1;
      return make_pair(new_node1, mid_data1);
    } else {
      // rightが空いているので、midをrightに移し、新しいnodeをmidに挿入する
      node->right = node->mid;
      node->data2 = node->data1;
      node->mid = new_node;
      node->data1 = mid_data;
      return make_pair(nullptr, -1);
    }
  } else if (node->data2 == -1 || x < node->data2) {
    pair<Node *, int> temp = insert_node(node->mid, x);
    Node *new_node = temp.first;
    int mid_data = temp.second;
  }
}

struct TwoThreeTree {
  Node *root;

  bool search(int x) {
    Node *curr = root;
    while (curr != nullptr) {
      if (curr->data1 == x || (curr->data2 != -1 && curr->data2 == x)) {
        return true;
      } else if (x < curr->data1) {
        curr = curr->left;
      } else if (curr->data2 == -1 || x < curr->data2) {
        curr = curr->mid;
      } else {
        curr = curr->right;
      }
    }
    return false;
  }
};

Q13 「赤黒木の満たす性質を述べよ」

すべてのノードは赤または黒で塗られている

根は黒である

すべての葉は黒である

赤ノードの子はどちらも黒

あるノードからそのノードの葉にいたるパスには、すべて同じ数の黒ノードが存在する

Q14 「AVL木の満たす性質を述べよ」

木 $t$ のbiasをbias($t$) = 左の木の高さ - 右の木の高さとしたとき、すべての部分木が $-1 < bias(t) < 1$ を満たす

Q15 「赤黒木の木の高さを評価せよ」

ある部分木 $x$ における葉までのパスに含まれる黒ノードの数を $bh(x)$ とする。まず、$x$ は少なくとも $2^{bh(x)} - 1$ 個のノードを含むことを示す。 $x$ の根が黒の場合左右の部分木はすくなくとも $2^{bh(x) - 1} - 1$ 個持ち、$x$ の根が赤の場合は左右の部分木は少なくとも $2^{bh(x)} - 1$ 個のノードを含む。よって、$x$ は少なくとも $2^{bh(x) - 1} - 1 + 2^{bh(x) - 1} - 1 + 1 = 2^{bh(x)} - 1$ 個のノードを含む。

$$n \geq 2^{bh(x)} - 1$$

また赤黒木の性質から、 $bh(x)$ は、木の高さを $h$ とすると、 $bh(x) \geq \frac{h}{2}$ となる。

$$n \geq 2^{\frac{h}{2}} - 1$$
$$h \leq 2\log_{2}(n + 1)$$

理想的な完全2分木の高さは $\log_{2}(n+1)$ なので、赤黒木は最悪2倍高くなる。

Q16 「AVL木の木の高さを評価せよ」

高さhの部分木が含むノードの数の最小値を$f(h)$とおくと、$f(h + 2) = f(h + 1) + f(h) + 1$ であり、$f(0) = 0, f(1) = 1$ であるから、$F(h) = f(h) + 1$ とおくと、$F(h) = \frac{1}{\sqrt{5}} ((2-\beta)\alpha^{h} - (2-\alpha)\beta^{h})$, ($\alpha = \frac{1+\sqrt{5}}{2}, \beta = \frac{1-\sqrt{5}}{2}$)となる。よって、$F(h) \sim \frac{2-\beta}{\sqrt{5}} \alpha^{h}$ と近似すると、$n + 1 = \frac{2-\beta}{\sqrt{5}} \alpha^{h}$ となり、$h = \log_{\alpha}(n+1) \sim 1.44\log_{2}(n+1)$ を得る。

Q17 「ハッシュの概要を述べよ」

要素の内容から直接データが格納されている場所を計算することで、要素の参照・追加・削除をO(1)で行うアルゴリズム

Q18 「チェイン法の概要を述べよ」

データ格納セルにリストをつなげることによって、おなじハッシュ関数値を返す複数のデータを一つの場所におくハッシュ。リスト内部での探索には線形の時間がかかるので、あまりに多くのデータが一つのリストに格納されてしまうと効率が低下する。

Q19 「チェイン法の計算量を求めよ」

参照・追加・削除の手間はリストの長さとおなじであり、バケットの数を$B$、格納されているデータの数を$N$とすると、平均してリストの長さは $\frac{N}{B}$ となるので、$O(\frac{N}{B} + 1)$ となる。バケットが十分大きければこれは定数とみなすことができる。

Q20 「チェイン法を実装せよ」

#include <iostream>
#include <list>
using namespace std;

template <typename T> struct ChainHash {
  int B;
  list<T> *table;

  ChainHash(int bucket_size) {
    B = bucket_size;
    table = new list<T>[B];
  }

  int hash(T key) { return key % B; }

  void insert(T key) {
    int index = hash(key);
    table[index].push_back(key);
  }

  void erase(T key) {
    int index = hash(key);

    for (auto it = table[index].begin(); it != table[index].end(); it++) {
      if (*it == key) {
        table[index].erase(it);
        break;
      }
    }
  }

  void print() {
    for (int i = 0; i < B; i++) {
      cout << i << ":";
      for (T key : table[i]) {
        cout << " --> " << key;
      }
      cout << endl;
    }
  }
};

int main() {
  ChainHash<int> ch(4);
  ch.insert(7);
  ch.insert(11);
  ch.insert(8);
  ch.insert(0);
  ch.insert(2);
  ch.insert(1);
  ch.insert(5);
  ch.erase(1);

  ch.print();
}

Q21 「開番地法の概要を述べよ」

ハッシュ関数の衝突が起きた時は、衝突が起きなくなるまで再ハッシュによって次の候補場所を計算して、衝突が起きない場所に格納する。理想的にはほぼランダムに異なる格納場所を返す関数が理想的である。

Q22 「開番値法の計算量を求めよ」

データ数をN、バケット数をBとする。

追加にかかる計算量

すべてのバケットにN/Bでデータが格納されていると仮定すると、新たにデータを挿入するときにちょうどi回ハッシュの衝突が起きる確率は、
$(\frac{N}{B})^{i} - (\frac{N}{B})^{i+1}$であり、その期待値を取ると、

\begin{align}
&\sum_{i=0}^{\inf} (i+1) \{(\frac{N}{B})^{i} - (\frac{N}{B})^{i+1}\} \\
=& \sum_{i=0}^{\inf} (\frac{N}{B})^{i} \\
=& \frac{B}{B-N}
\end{align}

なお、ここで$\sum_{k=0}^{\inf}x^{k} = \frac{1}{1-x} \quad (s.t. |x| < 1)$を用いた。

既存要素の参照・削除の計算量

この計算量は、空のハッシュに順次要素を追加していった時の計算量の平均であるので、

\begin{align}
\frac{1}{N} \sum_{i=0}^{N-1} \frac{B}{B-i} &\sim \frac{1}{N} \intercal_{0}^{N-1} \frac{B}{B-x} dx \\
                                           &= \frac{B}{N} \log_{e} (\frac{B}{B-N+1})
\end{align}

Q23 「開番地法を実装せよ」

要素を削除した際には、単に空にしてしまうと、後から挿入された要素を参照したいときに、単に挿入されていないだけなのか、再ハッシュによって別の場所に移動したのかが分からなくなってしまうので、特別なdeletedというラベルをしまっておく。参照の時にdeletedに当たった場合には、衝突があったものとして再ハッシュによる探索を続ける
追加するときにdeletedに当たった場合には、単に空だったものとしてその場所にデータを格納する

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename Key, typename Value> struct Node {
  Key key;
  Value val;
  bool is_dummy = false;

  Node() {}

  Node(Key key, Value val) {
    this->key = key;
    this->val = val;
  }
};

template <typename Key, typename Value> struct HashOpenAddress {
  Node<Key, Value> **cells;
  Node<Key, Value> *dummy;
  Value null;
  int B;
  int current_size = 0;

  HashOpenAddress(int bucket_size, Value null_value) {
    B = bucket_size;
    null = null_value;
    cells = new Node<Key, Value> *[B];
    dummy = new Node<Key, Value>();
    dummy->is_dummy = true;
  }

  int hash(Key key) { return key % B; }

  void insert(Key key, Value val) {
    if (current_size == B) {
      return;
    }

    int index = hash(key);
    Node<Key, Value> *node = new Node<Key, Value>(key, val);

    while (cells[index] != nullptr && cells[index]->key != key &&
           !cells[index]->is_dummy) {
      index = (index + 1) % B;
    }

    if (cells[index] == nullptr || cells[index]->is_dummy) {
      current_size++;
    }
    cells[index] = node;
  }

  void erase(Key key) {
    if (current_size == 0) {
      return;
    }

    int index = hash(key);

    while (cells[index] != nullptr) {
      if (cells[index]->key == key) {
        Node<Key, Value> *node = cells[index];
        cells[index] = dummy;
        current_size--;
      }
      index = (index + 1) % B;
    }
  }

  Value get(Key key) {
    int index = hash(key);
    int cnt;
    while (cells[index] != nullptr && cnt < B) {
      if (cells[index]->key == key) {
        return cells[index]->val;
      }
      index = (index + 1) % B;
    }
    return null;
  }
};

int main() {
  HashOpenAddress<int, int> hoa(10, -99);
  hoa.insert(0, 0);
  hoa.insert(1, 1);
  cout << hoa.get(1) << endl;
  hoa.erase(1);
  cout << hoa.get(1) << endl;
  hoa.insert(10, 2);
  cout << hoa.get(10) << endl;
}

Q24 「Union Findを実装せよ」

#include <iostream>
#include <vector>
using namespace std;

struct UnionTree {
  vector<int> parents, size;
  UnionTree(int n) {
    parents.resize(n, 0);
    size.resize(n, 0);
    for (int i = 0; i < n; i++) {
      makeTree(i);
    }
  }

  void makeTree(int x) {
    parents[x] = x;
    size[x] = 1;
  }

  int findRoot(int x) {
    if (parents[x] != x) {
      // 経路の圧縮を行うことで、findの走査を高速化する
      parents[x] = findRoot(parents[x]);
    }
    return parents[x];
  }

  bool isSame(int x, int y) { return findRoot(x) == findRoot(y); }

  bool unite(int x, int y) {
    x = findRoot(x);
    y = findRoot(y);

    if (x == y) {
      return false;
    } else {
      if (size[x] > size[y]) {
        parents[y] = x;
        size[x] += size[y];
      } else {
        parents[x] = y;
        size[y] += size[x];
      }
      return true;
    }
  }
};

Q25 「Union Findの計算量を求めよ」

マージは、マージされる木をマージする側の木の根の下につけるだけでよいのでO(1)。Findのさいには、親へ向かうポインタをたどって根のIDを調べればよいので、木の深さが計算量となる。