Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 101. Symmetric Tree

leetcode
tags: leetcode

問題

アイデア

与えられた木が左右対称な木か判断する問題です．

これは与えられた木の部分木も左右対称となるので，その結果を用いて解くことにします．

解法1(recursive)

下の図のようになっているかを再帰的に関数を使って確かめます．

  • 根が空ならtrue
  • 空でないなら左右のノードを使って以下のように確かめます
    • 左右共にない(nullptr)ならtrue
    • 左右のどちらかしかないならfalse
    • 左右の値が同じ
      • 左の左==右の右
      • 左の右==右の左

計算量

ノードの数は$N$とします

  • 時間計算量
    • (大体)各々のノードで関数を実行するので$O(N)$
  • 空間計算量
    • 再帰の深さが$O(\log N)$なので$O(\log N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    if (!root)
      return true;
    return isMirror(root->left, root->right);
  }
private:
  bool isMirror(TreeNode* left, TreeNode* right) {
    if (!left && !right)
      return true;
    if (!left || !right)
      return false;
    return (left->val == right->val) && isMirror(left->left, right->right) && isMirror(left->right, right->left);
  }
};

解法2(iterative)

BFSのときはQueue, DFSのときはStackが有効です

今回は前者で探索しているのでQueueを選択して解きます．

計算量

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  bool isSymmetric(TreeNode* root) {
    if (!root)
      return true;
    queue<TreeNode*> q_left, q_right;
    q_left.push(root->left);
    q_right.push(root->right);
    
    while (!q_left.empty() && !q_right.empty()) {
      auto left = q_left.front();
      auto right = q_right.front();
      q_left.pop(), q_right.pop();
      
      if (!left && !right)
        continue;
      if (!left || !right)
        return false;
      if (left->val != right->val)
        return false;
      
      q_left.push(left->left);
      q_left.push(left->right);
      q_right.push(right->right);
      q_right.push(right->left);
    }
    return true;
  }
};

# LeetCode Hard 145. Binary Tree Postorder Traversal

leetcode
tags: leetcode

風邪は治ったけど，花粉症がキツイ．

次の総理大臣は花粉症を撲滅してほしい．

問題

アイデア

木を探索する際の順序として以下の図ように

  • Inorder(左→根→右)
  • Preorder(根→左→右)
  • Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

解法1(recursive)

InorderとPreorderと同じ要領でやるだけです．

Postorderは左，右，根の順番に答えの配列に格納します．

計算量

ノードの数を$N$とします．

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • 再帰の深さを考えても答えの配列の方が大きいので$O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
    if (!root)
      return {};
      
    vector<int> res;      
    helper(root, res);
    return res;
  }
private:
  void helper(TreeNode* node, vector<int>& res) {
    if (!node)
      return;
    
    if (node->left)
      helper(node->left, res);
    if (node->right)
      helper(node->right, res);
    res.push_back(node->val);
  }
};

解法2(iterative)

再帰だと簡単に書けるけど反復的に書くのは面倒ですね...

Post-Orderの場合はスタックを2つ使うと上手く行きます．

注意するのはスタックはLIFO(Last-in First-out)なので，最後に入れたものが最初に出ます．

下のコードでは最初のwhileで，左，右の順番にスタックにノードを入れているので，右，左の順番に出ます．その結果根→右→左にrevResにノードが入っており，これを取り出すと求める順番となっています．

計算量

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • 新たなスタックに必要な空間計算量が$O(N)$です
    • よって，$O(N)$
    • もし，答えを配列で格納する必要がない場合は$O(\log N)$で抑えられますが，余分に必要です

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> postorderTraversal(TreeNode* root) {
    if (!root)
      return {};
    
      stack<TreeNode*> nodeStack;
    stack<int> revRes;
    vector<int> res;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
      auto curNode = nodeStack.top();
      nodeStack.pop();
      revRes.push(curNode->val);
      if (curNode->left)
        nodeStack.push(curNode->left);
      if (curNode->right)
        nodeStack.push(curNode->right);
    }
    while (!revRes.empty()) {
      res.push_back(revRes.top());
      revRes.pop();
    }
    return res;
    }
};

# LeetCode Medium 144. Binary Tree Preorder Traversal

leetcode
tags: leetcode

非常に久しぶりです．

案の定，風邪を引いていました．皆さんも季節の変わり目には気を付けて下さい^_^(コロナじゃなくてよかったーーーーーー)

問題

アイデア

木を探索する際の順序として以下の図ように

  • Inorder(左→根→右)
  • Preorder(根→左→右)
  • Postorder(左→右→根)

があります

ノードが5つの木の場合を図示すると以下の通りです

解法1(recursive)

まずは根の値を答えの配列に入れ，次に左，右の部分木を見てそのノードの値を入れる再帰関数を書きます．

計算量

ノードの数を$N$として

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • 再帰関数の深さに応じて$O(\log N)$
    • 答えを格納する配列の大きさが$O(N)$
    • $O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
    if (!root)
      return {};
    
    vector<int> res;
    getNodeFromTree(root, res);
    return res;
  }
private:
  void getNodeFromTree(TreeNode* node, vector<int>& res) {
    if (!node)
      return;
    res.push_back(node->val);
    getNodeFromTree(node->left, res);
    getNodeFromTree(node->right, res);
  }
};

解法2(iterative)

上記の解答をwhileなどを使って反復的に書くだけです

std::stackを使うことで再帰関数を表現できます．

  • 最初に答えを格納する配列を作ります
  • 次にノードを入れるスタックを作ります
  • まずは根をスタックに入れます．
  • スタックが空になるまで以下の動作を繰り返します
    • スタックの先頭のノードの値を配列に入れて，スタックから削除する
    • そのノードの右のノードがあればスタックに入れる
    • そのノードの左のノードがあればスタックに入れる

計算量

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • 再帰が必要のない分時間計算量は少ないですが，答えを格納する配列の分は変わらず必要です．
    • $O(N)$

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  vector<int> preorderTraversal(TreeNode* root) {
    if (!root)
      return {};
    
    vector<int> res;
    stack<TreeNode*> nodeStack;
    nodeStack.push(root);
    while (!nodeStack.empty()) {
      auto curNode = nodeStack.top();
      nodeStack.pop();
      res.push_back(curNode->val);
      if (curNode->right)
        nodeStack.push(curNode->right);
      if (curNode->left)
        nodeStack.push(curNode->left);
    }
    return res;
  }
};

# CMU DB 7. Trees Indexes I

CMU DB
tags: CMU DB

今回はB+木について扱うようです．

授業

データ構造は

  • internal meta-data
  • core data storage
  • temporary data structures
  • table indexes

に使われる．今回はtable indexesについて扱う．

table indexはテーブルの特性の複製で，効率的にアクセスできるように整列されている

DBMSはテーブルの内容とindexが論理的に同期されていることを保証している．

DBMSはそれぞれのクエリを実行するために使う最高のindexを見つけることが仕事．

データベースごとのindexの数にはトレードオフがある．

  • storage overhead
  • maintenance overhead

B+ Tree

  • B-tree
  • B+ tree
  • B* tree
  • B-link-tree

というのがある．

B+ treeは自己均衡型の木構造でデータを整列した状態にし，探索，連続アクセス，挿入，削除を$O(\log n)$で出来る

根以外のノードは少なくとも半分は埋まっている([M/2-1 <= #keys <= M-1])

[<node*>|<key>]のように並んでいる．

  • 全てのB+ treeノードはkey/valueのペアの配列によって構成されている
    • keysはインデックスが基づくattributeに由来する
    • valuesはそのノードがinnder nodes とleaf nodesのどちらに分類されているかで異なる
    • 配列はよく整列されたkeyの順序で保持されている

leaf nodeのvaluesに関して以下の2種類のアプローチがある．

  • record ids
    • index entryの対応するタプルのポインタへのポインタ

  • tuple data

    • タプルの実際の中身はleaf nodeに格納されている
    • secondary indexはvalueとしてrecord idを保持する必要がある

  • B-Treeは全てのノードにkeyとvalueがある

  • B+ treeはleaf nodesしかvalueを持たず，inner nodesは探索処理の手伝うだけ

このリンクが使える．

primary keyによって指定された整列順序でテーブルに格納される．heapでもindex管理でも大丈夫

DBMSにはいつもclustered indexを使っているものもある．もしprimary keyをテーブルが持っていないとき，DBMSは自動で隠れた行idのprimary keyを作る

他のDBMSはclustered indexを全く使えない．

Design Decisions

ストレージが遅いほど，最適なノードのサイズは大きくなる．

仕事量によって最適なサイズは異なることがありうる．

いくつかのDBMSでは半分満杯のときにノードを必ずしも統合しない．

統合の処置を遅らせることは再編の量を減らすかも知れない．

underflowが生じることを許して，定期的に全ての木を再構築する方もまた良い可能性がある．

変数の長さに関して以下の取り組み方がある．

  • pointers
  • variable
  • length nodes
  • padding
  • key map/indirection

一意でないindexには以下の取り組みがある．

  • duplicate keys
  • value lists

intra-node searchには以下の取組がある．

  • linear
  • binary
  • interpolation

Optimizations

  • prefix compression
    • 同じleaf nodeにある整列されたkeyは同じprefixを持つ傾向にある
    • 共通のprefixを除いて，一意なsuffixのみをkeyに保持する
  • suffix truncation
    • inner nodeにあるkeyのindexへ繋がるように正しく道案内するために必要な最低限のprefixのみを保存する
  • bulk insert
    • B+ treeを構築する最速な方法はkeyを整列し，下からindexを構築すること
  • pointer swizzling
    • ノードはindexの他のnodeを参照するためにpage idを使う
    • DMBSは探索の間にpage tableからメモリの場所を下に入れなければならない．
    • もしページがbuffer poolピン留めされていたら，page idの代わりに生ポインタを保持することが可能
    • これはpage tableからアドレスを探すことを避ける

結論

由緒あるB+ treeはいつもDBMSによって良い選択肢である．

感想

頭にあまり入っていない...多分風邪引いた...

今回はB+ treeの話ばかりであまり面白くなかった

# LeetCode Medium 287. Find the Duplicate Number

leetcode
tags: leetcode

問題

アイデア

要素数がn + 1の整数の配列が与えられた時，要素は[1, n]であり，鳩の巣原理より少なくとも1つの要素は重複しています．

このうち，重複している要素を探せというもの．

注意点は

  • 配列を操作してはいけない．
    • つまりstd::sortは使えない．
  • 空間計算量は$O(1)$しか許されていない．
    • つまり新たなデータ構造が使えない．
  • 時間計算量は$O(n^{2})$よりも小さい必要がある．
    • つまり2重ループも使えない．
  • 1つしか重複した数はないが，それは1つ以上重複している可能性がある．

解法

この問題ではcycle detectionを行うと空間計算量が$O(1)$で済みます．

配列の要素は[1, n]です．つまり，これらの要素は必ずある要素の添字となります．つまり，ある要素を添え字とする配列の要素から，その要素を添え字とする要素と飛ぶとすると[1, n]の添字内で循環が発生します．

また，0は要素として現れないのでnums[0]は循環の一部とはなりえません．つまり，この問題は循環がどこで生じているのかを見つければ良いのです．

つまり，func(index) = elementとなるような写像関係を考えれば良いです．例えば

  • [1,3,4,2,2]
    • 0 -> 1, 1 -> 3, 2 -> 4, {3, 4} -> 2
    • という写像関係があります．このとき，
    • 0 -> 1 -> 3 -> 2 -> 4 -> 2 -> 4 -> 2 ->...となり途中から2, 4が連続します．このような数列の最初の数が今回求めるものです．

これからすることを図示すると以下のようになります．

  • ループの開始点に行くまでにxステップ必要で，ループ内で両者が会う場所は開始点からyステップ必要で，両者が会った場所からループの開始点まではzステップ必要とします．
  • 最初のループでは1ステップごと進む要素(tortoise)と2ステップごと進む要素(hare)を使って，ステップ内に片方の要素を入れます．
    • このときにtortoiseはx+y動きます．
    • また，hareはx+2y+z動きます．
    • ここから，hareはtortoiseの2倍のステップ動くので2(x+y)=x+2y+z，つまりx=zとなります．
  • 2つ目のループでは上の結果を利用します．
    • 上よりx=zであり，tortoiseを初期値に戻し，既にmeeting pointにいるhare一緒に1ステップずつ動かします．
    • そうするとループの開始点で両者は会うことができ，これが求める答えです．

計算量

配列の長さは$N$として

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

C++

class Solution {
public:
  int findDuplicate(vector<int>& nums) {
    if (nums.size() <= 1)
      return -1;
    
    int tortoise = nums[0];
    int hare = nums[nums[0]];
    while (tortoise != hare) {
      tortoise = nums[tortoise];
      hare = nums[nums[hare]];
    }
    
    hare = 0;
    while (hare != tortoise) {
      hare = nums[hare];
      tortoise = nums[tortoise];
    }
    return hare;
  }
};