１０．３ 最大・最小ヒープ

buildMaxHeap() と maxHeapify() が問題文に書いてあり、そのままの実装となります。

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
 
static inline int left(int i) {
  return 2 * i;
}

static inline int right(int i) {
    return 2 * i + 1;
}

static inline void maxHeapify(vector<int>& A, int i) {
  const int l = left(i);
  const int r = right(i);

  const int H = A.size() - 1;
  int largest = 0;
  if (l <= H && A[l] > A[i]) {
    largest = l;
  } else {
    largest = i;
  }

  if (r <= H && A[r] > A[largest]) {
    largest = r;
  }
    
  if (largest != i) {
    swap(A[i], A[largest]);  
    maxHeapify(A, largest);
  }
}

static void buildMaxHeap(vector<int>& A) {
  const int H = A.size() - 1;
  for (int i = H / 2; i > 0; i--) {
    maxHeapify(A, i);
  }
}

static vector<int> A;

int main() {
  int H;
  cin >> H;

  A.resize(H + 1);

  int k;
  for (int i = 1; i <= H; i++) {
    cin >> k;
    A[i] = k;
  }
  
  buildMaxHeap(A);
  
  for (int i = 1; i <= H; i++) {
    cout << " " << A[i];
  }
  cout << endl;

  return 0;
}

１０．２ 完全二分木

ヒープ編に突入。今回は問題文通りの実装です。parent, left, right が単純な計算で決定するのが面白いですね。なお、解説の実装では、木の実装が int の配列になっており、自分の実装は無駄な箇所が多々あります。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

static vector<Node> tree;

int main() {
  int h;
  cin >> h;

  tree.resize(h + 1);

  int k;
  for (int i = 1; i < tree.size(); i++) {
    cin >> k;
    tree[i].key = k;
  }

  int parent, left, right;
  for (int i = 1; i < tree.size(); i++) {
    parent = i / 2;
    if (parent != 0) {
      tree[i].parent = &tree[parent];
    }
    left = 2 * i;
    if (left < tree.size()) {
      tree[i].left = &tree[left];
    }
    right = 2 * i + 1;
    if (right < tree.size()) {
      tree[i].right = &tree[right];    
    }
  }

  for (int i = 1; i < tree.size(); i++) {
    auto& node = tree[i];
    printf("node %d: key = %d, ", i, node.key);
    if (node.parent) {
      printf("parent key = %d, ", node.parent->key);
    }
    if (node.left) {
      printf("left key = %d, ", node.left->key);
    }
    if (node.right) {
      printf("right key = %d, ", node.right->key);
    }
    printf("\n");
  }

  return 0;
}

９．４ 二分探索木（写経編）

これはアカンかったです。次節点の探索のところ、ややこしすぎませんか？

あっそういえばポインタの参照を久しぶりに使いました。（rootの入れ替えのところ）

#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

static Node* find(Node* node, int v) {
  while (node != nullptr && node->key != v) {
    if (node->key > v) {
      node = node->left;
    } else {
      node = node->right;
    }
  }
  return node;
}

static Node* getSuccessor(Node* x) {
  if (x->right) {
    x = x->right;
    while (x->left) {
      x = x->left;
    }
    return x;
  }
  
  Node* y = x->parent;
  while (y && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

static void deleteNode(Node*& root, int v) {
  Node* z = find(root, v);
  Node* y;
  if (!z->left || !z->right) {
    y = z;
  } else {
    y = getSuccessor(z);  
  }

  Node* x;
  if (y->left) {
    x = y->left;
  } else {
    x = y->right;
  }
  
  if (x) {
    x->parent = y->parent;
  }
  
  if (!y->parent) {
    root = x;    
  } else if (y == y->parent->left) {
    y->parent->left = x;
  } else {
    y->parent->right = x;
  }
  
  if (y != z) {
    z->key = y->key;  
  }
  delete y;
}

void preorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

int main() {
  int n;
  cin >> n;

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else if (command[0] == 'f') {
      scanf("%d", &v);
      Node* found = find(TREE.root, v);
      cout << (found ? "yes" : "no") << endl;
    } else if (command[0] == 'd') {
      scanf("%d", &v);
      deleteNode(TREE.root, v);
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}

９．３ 二分探索木：探索

お仕事でいろいろとやられているので間が空いてしまいました。

今回のお題は前回の内容を引き継いでいるので、あとは探索機能を入れるだけでした。

※20180417追記：巡回出力のところがバグっていたので直しました

#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

static bool find(const Node* node, int v) {
  if (node == nullptr) {
    return false;
  }
  if (node->key > v) {
    return find(node->left, v);
  } else if (node->key < v) {
    return find(node->right, v);
  }
  return true;
}

void preorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (!node) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

int main() {
  int n;
  cin >> n;

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else if (command[0] == 'f') {
      scanf("%d", &v);
      bool found = find(TREE.root, v);
      cout << (found ? "yes" : "no") << endl;
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}

９．２ 二分探索木：挿入

問題に書いてあった解説どおりの実装です。delete を呼んでないのが気持ち悪いですが、まあ良いでしょう。良くないか。

#include <iostream>
#include <cstdio>
#include <memory>

using namespace std;

struct Node {
  int key;
  Node* parent;
  Node* left;
  Node* right;
  
  Node(int key = -1) : key(key), parent(nullptr), left(nullptr), right(nullptr) {};
};

struct Tree {
  Node* root;  
  
  Tree() : root(nullptr) {};
};

static void insert(Tree& tree, int v) {
  Node* z = new Node(v);
  Node* x(tree.root);
  Node* y(nullptr);
  while (x != nullptr) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }
  
  z->parent = y;
  if (y == nullptr) {
    tree.root = z;
  } else if (z->key < y->key) {
    y->left = z;
  } else {
    y->right = z;
  }
}

void preorderWalk(const Node* node) {
  if (node->key == -1) {
    return;
  }
  cout << " " << node->key;
  if (node->left != nullptr) {
    preorderWalk(node->left);
  }
  if (node->right != nullptr) {
    preorderWalk(node->right); 
  }
}

void inorderWalk(const Node* node) {
  if (node->key == -1) {
    return;
  }
  if (node->left != nullptr) {
    inorderWalk(node->left);
  }
  cout << " " << node->key;

  if (node->right != nullptr) {
    inorderWalk(node->right); 
  }
}

static Tree TREE;

int main() {
  int n;
  cin >> n;

  string command;
  int v;
  for (int i = 0; i < n; i++) {
    cin >> command;
    if (command[0] == 'i') {
      scanf("%d", &v);
      insert(TREE, v);
    } else {
      inorderWalk(TREE.root);
      cout << endl;
      preorderWalk(TREE.root);
      cout << endl;
    }
  }

  return 0;
}

８．５ 木巡回の応用：木の復元

ちょっと間が空いてしまいました。自力で考えたとっkは、すべての木を復元しようとしたのですが、NGでした。ということでこちらは写経となっております。シンプルな再帰とアルゴリズムを思いつくにはどうしたら良いんでしょうねえ。。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

static vector<int> preorder(100), inorder(100);

static void inputOrder(vector<int>& order, int num) {
  for (int i = 0; i < num; i++) {
    cin >> order[i];
  }
}

static int current = 0, outIndex = 0;

static int next() {
  int c = preorder[current];
  current++;
  return c;
}

static int find(int c) {
  auto it = find(inorder.begin(), inorder.end(), c); 
  return distance(inorder.begin(), it);
}

static void reconstruction(int l, int r) {
  if (l >= r) {
    return;
  } 
  int c = next();
  int m = find(c);
  reconstruction(l, m);
  reconstruction(m + 1, r);

  if (outIndex != 0) {
    cout << " " << c;
  } else {
    cout << c;
  }
  outIndex++;
}

int main() {
  int n;
  cin >> n;

  inputOrder(preorder, n);
  inputOrder(inorder, n);
  reconstruction(0, n);

  cout << endl;

  return 0;
}

８．４ 木の巡回（手動編）

詳細は端折りますが、いろいろと難しく考えすぎて失敗しました。こんなシンプルな方法で巡回になるんですね。。

#include <iostream>
#include <vector>

using namespace std;

struct Node {
  int id;
  int parent;
  int left;
  int right;

  Node() : id(), parent(-1), left(-1), right(-1) {}
  };

static vector<Node> TREE(25);

static void inputNode(Node& node, int id) {
  node.id = id;
  cin >> node.left >> node.right;
}

static const Node& getRoot(const vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    if (tree[i].parent == -1) {
      return tree[i];
    } 
  }
}

static void getNextPreorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }

  cout << " " << node.id;
  
  if (node.left != -1) {
    getNextPreorder(tree, tree[node.left]);
  }

  if (node.right != -1) {
    getNextPreorder(tree, tree[node.right]);
  }
}

static void preorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Preorder" << endl;
  getNextPreorder(tree, root);
  cout << endl;
}

static void getNextInorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }
  
  if (node.left != -1) {
    getNextInorder(tree, tree[node.left]);
  }

  cout << " " << node.id;

  if (node.right != -1) {
    getNextInorder(tree, tree[node.right]);
  }
}

static void inorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Inorder" << endl;
  getNextInorder(tree, root);
  cout << endl;
}

static void getNextPostorder(const vector<Node>& tree, const Node& node) {
  if (node.id == -1) {
    return;
  }
  
  if (node.left != -1) {
    getNextPostorder(tree, tree[node.left]);
  }

  if (node.right != -1) {
    getNextPostorder(tree, tree[node.right]);
  }

  cout << " " << node.id;
}

static void postorderTreeWalk(const vector<Node>& tree, const Node& root) {
  cout << "Postorder" << endl;
  getNextPostorder(tree, root);
  cout << endl;
}

static void setupTree(vector<Node>& tree, int num) {
  for (int i = 0; i < num; i++) {
    Node& node = tree[i];
    if (node.left != -1) {
      tree[node.left].parent = node.id;
    }
    if (node.right != -1) {
      tree[node.right].parent = node.id;
    }
  }
}

int main() {
  int n;
  cin >> n;

  int id;
  for (int i = 0; i < n; i++) {
    cin >> id;
    inputNode(TREE[id], id);
  }

  setupTree(TREE, n);
  const Node root = getRoot(TREE, n);

  preorderTreeWalk(TREE, root);
  inorderTreeWalk(TREE, root);
  postorderTreeWalk(TREE, root);

  return 0;
}