二分木(Binary Search Tree)の実装 その1

アルゴリズム データ構造 golang

概要

シンプルな二分木をGolangで実装していきます。 二分木の動作は以下のURLがビジュアル化されていてわかりやすいです。

Binary Search Tree Visualization

まずは二分木のベースとして値の挿入をして木を作成し、 見つけたい値が木に含まれているかを判定する関数を作成します。

実装

木とノードの定義

type Node struct {
    Value int  // ノードの持つ値
    Left  *Node // 左側ノードへのポインタ
    Right *Node // 右側ノードへのポインタ
}

// 二分木として持つのはルートノードのみ
// ノードにアクセスするのはすべてルートからたどる
type Tree struct {
    Root *Node
}

代入処理

// TreeにNodeを加える
func (t *Tree) Insert(insertValue int) {
    if t.Root == nil {
        // 初回のNodeだった場合はTreeのRootとしてNodeを設定する
        // t.root = CreateNode(insertValue)
        t.Root = &Node{Value: insertValue}
    } else {
        parentNode := t.Root
        for {
            if insertValue >= parentNode.Value {
                // 右のノードを確認
                if parentNode.Right != nil {
                    // ノードが存在するならば移動
                    parentNode = parentNode.Right
                } else {
                    // ノードがまだ無ければノードを配置する
                    parentNode.Right = &Node{Value: insertValue}
                    break
                }
            } else {
                // 左のノードを確認して同様に代入OR移動
                if parentNode.Left != nil {
                    parentNode = parentNode.Left
                } else {
                    parentNode.Left = &Node{Value: insertValue}
                    break
                }
            }
        }
    }
}

テストの作成

値を代入して正しい位置にノードがあるかを判定するテストコードを作成し、正しく処理ができているか確認します。

ここでは 4, 2, 7, 6 の順に代入して目的の木ができているかを確認します。

f:id:itib:20211017145547p:plain
4, 2, 7, 6の順で代入した木

func TestCreateTree(t *testing.T) {
    var tree binary_search_tree.Tree
    tree.Insert(4)
    tree.Insert(2)
    tree.Insert(7)
    tree.Insert(6)

    if tree.Root.Value != 4 {
        t.Error("Failed")
    }
    if tree.Root.Left.Value != 2 {
        t.Error("Failed")
    }
    if tree.Root.Right.Value != 7 {
        t.Error("Failed")
    }
    if tree.Root.Right.Left.Value != 6 {
        t.Error("Failed")
    }
    if tree.Root.Right.Right != nil {
        t.Error("Failed")
    }
}

ディレクトリ構成

project
├ binary_search_tree
│ ├ binary_search_tree.go
│ └ binary_search_tree_test.go
└ go.mod

binary_search_tree.go

package binary_search_tree

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

// NodeたちにアクセスするのはすべてRootから
// BinarySearchTreeとして知っているのはRootの場所のみ
type Tree struct {
    Root *Node
}

// TreeにNodeを加える
func (t *Tree) Insert(insertValue int) {
    if t.Root == nil {
        // 初回のNodeだった場合はTreeのRootとしてNodeを設定する
        // t.root = CreateNode(insertValue)
        t.Root = &Node{Value: insertValue}
    } else {
        parentNode := t.Root
        for {
            if insertValue >= parentNode.Value {
                // 右のノードを確認
                if parentNode.Right != nil {
                    // ノードが存在するならば移動
                    parentNode = parentNode.Right
                } else {
                    // ノードがまだ無ければノードを配置する
                    parentNode.Right = &Node{Value: insertValue}
                    break
                }
            } else {
                // 左のノードを確認して同様に代入OR移動
                if parentNode.Left != nil {
                    parentNode = parentNode.Left
                } else {
                    parentNode.Left = &Node{Value: insertValue}
                    break
                }
            }
        }
    }
}

binary_search_tree_test.go

package binary_search_tree_test

import (
    "testing"

    "github.com/itiB/project/binary_search_tree"
)

func TestCreateTree(t *testing.T) {
    var tree binary_search_tree.Tree
    tree.Insert(4)
    tree.Insert(2)
    tree.Insert(7)
    tree.Insert(6)

    if tree.Root.Value != 4 {
        t.Error("Failed")
    }
    if tree.Root.Left.Value != 2 {
        t.Error("Failed")
    }
    if tree.Root.Right.Value != 7 {
        t.Error("Failed")
    }
    if tree.Root.Right.Left.Value != 6 {
        t.Error("Failed")
    }
    if tree.Root.Right.Right != nil {
        t.Error("Failed")
    }
}

go.mod

module github.com/itiB/project

go 1.16

テスト結果正常に木が作成できていることがわかりました。

❯ go test ./binary_search_tree
ok      github.com/itiB/project/binary_search_tree   0.004s

検索したい値が木に含まれているか判定

検索対象の値が木に含まれているか調べるには代入する場所を探すのと同様に木を探索していって一致する値が含まれているかを調べることで実装できます。

func (tree *Tree) Contains(findValue int) bool {
    // そもそも木がなければ含まれていない
    if tree.Root == nil {
        return false
    }

    cursor := tree.Root // 調べているノードを指す
    for {
        // ノードの値が検索対象の値なら発見
        if cursor.Value == findValue {
            return true
        } else {
            // ノードを移動する処理
            // もし進むべき方向にノードがないならば値は含まれていないとしてfalse
            if findValue >= cursor.Value {
                if cursor.Right != nil {
                    cursor = cursor.Right
                } else {
                    return false
                }
            } else {
                if cursor.Left != nil {
                    cursor = cursor.Left
                } else {
                    return false
                }
            }
        }
    }
}

テストの作成

木を作成し、代入した値が含まれているかのテストを記述します。

func TestFindTree(t *testing.T) {
    var tree binary_search_tree.Tree
    tree.Insert(4)
    tree.Insert(2)
    tree.Insert(7)
    tree.Insert(6)
    tree.Insert(-5)

    if !tree.Contains(4) {
        t.Errorf("Failed")
    }
    if !tree.Contains(6) {
        t.Errorf("Failed")
    }
    if !tree.Contains(-5) {
        t.Errorf("Failed")
    }
    if tree.Contains(5) {
        t.Errorf("Failed")
    }
    if tree.Contains(500000000000) {
        t.Errorf("Failed")
    }
}

❯ go test ./binary_search_tree
ok      github.com/itiB/project/binary_search_tree   0.004s

まとめ

二分木のベースとなる処理を作成することができました。 次は削除処理を作成します。

Base64デコーダーを作る

Python

本記事は以前筆者のqiitaに投稿していた記事を移動させたものです。

Base64デコーダーを作る - Qiita

とあるCrackmeでcustom_base64なるものでエンコードされた文字列が出てきた...
Flagを手に入れるためにはこれをデコードして元の文字列を見つけなきゃいけない． custom_base64とはなんなのか...答えを見つけるために，我々はアマゾンの奥地へと...

概要

Base64の仕組みの中で000000 ~ 111111を文字に置き換えた辞書が存在する． 通常のBase64では順番に ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ をあてはめた辞書が使われている． これを指定した辞書に入れ替えたものがcustom_base64関数の中身であった． Base64を実装する記事を参考に本記事ではPythonでデコーダーを実装する．

Base64の仕組み

エンコード

大まかにBase64のエンコードの処理を確認します．詳しくは他サイトを参照．

  1. 変更したい文字列(ASCII)をバイナリ(2進数)に変換
  2. バイナリを6bitづつに分割
  3. 分割した際に最後が6bitより少なくなるため，6bitになるように0を追加する
  4. 変換表を用いて6bitを文字に変換
  5. 4biteずつBase64では出力するために文字数が4の倍数文字になるよう"="を付け足す
  6. base64の文字列の完成!!

デコード

エンコードの仕組みがわかればデコードは簡単！基本的には逆の手順を踏むだけ！

  1. 付け足された"="を削除
    • SG9nZUhvZ2U= → SG9nZUhvZ2U
  2. 変換表を用いて文字をバイナリに変換してつなげる．
    • SG9nZUhvZ2U → 010010 000110 111101 100111 011001 010100 100001 101111 011001 110110 010100
  3. バイナリを8bitずつに分割，エンコード3. で付け足された0が余るのでそれらを削除
    • 01001000 01101111 01100111 01100101 01001000 01101111 01100111 01100101 00
  4. 2進数bitをASCIIに変換
01001000 → H
01101111 → o
01100111 → g
01100101 → e
01001000 → H
01101111 → o
01100111 → g
01100101 → e
  1. デコード完了！

プログラムにしてみる

import sys
import argparse
BYTE_SIZE = 8

# 000000 -> 111111まで1文字ずつ辞書型リストを作成する関数
def makeDict(base64Dict_seed):
    dictionary = {}

    for i in range(0, 64):
        dictionary[format(i, '06b')] = base64Dict_seed[i]

    return dictionary


# 文字列s をn文字で区切ってリスト化する関数
def split(string, n):
    split_list = []

    for i in range(0, len(string), n):
        split_list.append(string[i:i+n])

    return split_list


# 文字列がn文字なかったらn文字になるように`c`を足す
def fillBlank(s, n, c):
    mod = len(s) % n

    if mod == 0:
        return s
    else:
        margin = n - mod
        return s + c * margin


# 辞書の値を渡すと辞書のキーを返す
def getValue(key, items):
    for v in items.items():
        # print(v[1])
        if v[1] == key:
            # print(v)
            return v[0]
    return ''


def main():
    # -kをつけるとカスタム辞書を入力できる
    parser = argparse.ArgumentParser(
    description='custom Base64 Decoder')
    parser.add_argument('-k', '--key', help="Use custom Seed to encrypt in base64 ", \
        default="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/")
    parser.add_argument('text', help='base text')
    args = parser.parse_args()


    # 0. 辞書を作る
    base64Dict = makeDict(args.key)


    # 1. '='をはずす
    text = args.text.replace("=", '')

    binStr = ""


    # 2. 変換表を用いて文字をバイナリに変換してつなげる．
    for i in text:
        binStr += getValue(i, base64Dict)

    # 3. バイナリを8bitずつに分割，エンコード3. で付け足された0が余るのでそれらを削除
    splitCount = 8
    s = split(binStr, splitCount)

    if (len(s[-1]) != 8):
        s.pop(-1)


    # 4. 2進数bitをASCIIに変換
    result =""

    for c in s:
        print(c + " → " + chr(int(c, 2)))
        result += chr(int(c, 2))

    print(result)

if __name__ == "__main__":
    main()

使い方

$ python3 customBase64Decoder.py <Base64テキスト>
$ python3 customBase64Decoder.py -k <Custom辞書> <Base64テキスト>
$ python3 customBase64Decoder.py SG9nZUhvZ2U=
$ python3 customBase64Decoder.py -k xEPOKnvADqeG0m1VkZ47CM653jrtbzLsTc2ypoYUSWJ9ludQig+awf8XF/RNHBhI 4vBUjCcQj8C=

HogeHoge

まとめ

Base64完全に理解した． これでオリジナルBase64つくって秘密の通信ができちゃうね，やったね

サンプルコードはGitHubに置いてあります

参考文献

base64ってなんぞ？？理解のために実装してみた - qiita https://qiita.com/PlanetMeron/items/2905e2d0aa7fe46a36d41

M5StickCを動かしてみる

本記事は筆者が以前Qiitaに投稿していた記事を移動させたものです。

とりあえず動かせるとこまでやりました．

今回はArduino IDEで動かしてみます． Image from Gyazo

環境

  • Windows10
  • M5StickCがある

環境つくるよ

必要なものをインストール

  1. Arduino IDE
    https://www.arduino.cc/en/Main/Software
  2. USB to Serial Driver
    https://m5stack.oss-cn-shenzhen.aliyuncs.com/resource/drivers/CP210x_VCP_Windows.zip

Arduino IDEはサイトに飛んで"Download the Arduino IDE"より，対応するものをダウンロードしてインストールしてください．
USB to Serial Driverはリンクをクリックするとzipがダウンロードされます．
解凍すると中にいくつかのファイルがあると思います．対応するexeを選んで実行してください．

バージョン インストーラ
Windows10 32ビット版 CP210xVCPInstaller_x86_v6.7.0.0.exe
Windows10 64ビット版 CP210xVCPInstaller_x64_v6.7.0.0.exe
Windows7 CP210xVCPInstaller_Win7_v5.40.24.exe

うまくUSB to Serial Driverが入ったか実際にM5StickCをつないで確認していきます．

  1. . M5StickCをUSBで接続，
  2. . Windowsのデバイスマネージャを起動
  3. . ポートの中にUSB Serial Portが現れるはずです．(COM*)はUSBを刺したポート等で変わると思います． Image from Gyazo

Arduino IDEの設定

Arduino IDEを開いて実際にM5StickCを動かせるように準備していきます．

  1. . "ファイル -> 環境設定" を開く
  2. . "追加ボードマネージャのURL" に
    https://dl.espressif.com/dl/package_esp32_index.json を入力してOK
  3. . "ツール -> ボード"Ard...." -> ボードマネージャ" を開く
  4. . 検索バーで"esp32"を検索
  5. . でてきたのをインストールしたのち閉じる Image from Gyazo
  6. . "スケッチ -> ライブラリをインクルード -> ライブラリを管理" を開く
  7. . 検索バーでm5stickを検索，インストールしたのち閉じる Image from Gyazo
  8. . "ツール -> ボード -> M5Stick-C" を選ぶ
  9. . ツールのなかにボード情報とかが表示されるようになった Image from Gyazo

テストプログラムを動かしてみる！

"ファイル -> スケッチ例 -> M5StickC" のなかに様々なテストプログラムがあるので好きなものを選んでください．

ファイルとかの下にある右向きの矢印を押すとプログラムがコンパイルされ転送されます！

まとめ

かなりはやくここまで来れました． テストプログラムをたくさん用意してくれているのでそれで遊んでるだけでも結構たのしいです． こっからいろいろプログラム頑張って書いていきます． また気が向いたら記事にします．

言いたいこと等あれば以下まで Twitter: https://twitter.com/itiB_S144

参考記事

いろいろとM5StickCについて検証してくださっているわかりやすい記事様↓↓ Lang-ship: https://lang-ship.com/blog/

qiita.com