変数の名前をアルファベット順に出す
二分探索木とは、小さい値を左に、大きい値を右に置いて、探す範囲を半分ずつ減らせる木です。木を作って探し、順にたどることができるようになります。
コンパイラは、プログラムに出てくる変数の名前を覚え、あとで一覧にします。名前を木に入れておくと、探すのも、アルファベット順に出すのも、速くできます。
このレッスンのゴール
メモ
二分探索木を作り、キーを探して、順にたどることができる。
重要な言葉
| ことば | いみ |
|---|---|
| 木 | ノードが枝でつながった、上から下への形 |
| 根 | 木の一番上のノード |
| 葉 | 子を持たない、一番下のノード |
| 二分探索木 | 左は小さく、右は大きいキーを置いた木 |
| 中順 | 左、自分、右の順にたどること |
| 高さ | 根から葉まで、一番長い道にあるノードの数 |
学生が入力するセルは、このプレビューでは空白です。
二分探索木は、左が小さく右が大きい
木のノードは、最大2つの子を持ちます。左の子の木は、自分より小さいキーだけ、右の子の木は、大きいキーだけです。
この決まりは、どのノードでも守られます。だから探すとき、比べるたびに、残りの半分近くを捨てられます。
木に名前を入れるコード
class Node:
def __init__(self, key):
self.key = key
self.left = None # 小さいキーの木
self.right = None # 大きいキーの木
def insert(node, key):
if node is None:
return Node(key) # 空の場所に、新しい葉を置きます。
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
root = None
for name in ["total", "i", "unused", "step", "main"]:
root = insert(root, name)
print(root.key, root.left.key, root.right.key)
# 最後に "fare" を insert して、root.left.left.key を出してみましょう。
式も木になる
コンパイラは、式も木にします。2 + 3 4 では、掛け算が足し算より下になり、先に計算されます。(2 + 3) 4 では、足し算が下になります。
同じ文字の並びが、括弧で別の木になります。ラボの電卓で、答えが変わるのを見ましょう。
コンパイラのフォルダに入る
cd ~/compilerここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
電卓を用意する
makeここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
掛け算が下にある木
echo "2 + 3 * 4" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
足し算が下にある木
echo "(2 + 3) * 4" | ./calcここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
中順にたどると、小さい順に出る
ノードを訪ねる順は、左の木、自分、右の木です。これを中順と言います。
木は、小さな木でできています。だから、この作業は自分自身を呼ぶ関数で書けます。空の木が来たら、そこで止まります。
例: total の木を中順にたどる
| 訪ねる順 | 訪ねる所 | 出る名前 |
|---|---|---|
| 1 | i の左は空 | （なし） |
| 2 | i | i |
| 3 | step の左の main | main |
| 4 | step | step |
| 5 | total | total |
| 6 | unused | unused |
学生が入力するセルは、このプレビューでは空白です。
中順にたどるコード
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(node, key):
if node is None:
return Node(key)
if key < node.key:
node.left = insert(node.left, key)
else:
node.right = insert(node.right, key)
return node
def walk(node):
if node is None:
return [] # 空の木には、何も並びません。
return walk(node.left) + [node.key] + walk(node.right)
root = None
for name in ["total", "i", "unused", "step", "main"]:
root = insert(root, name)
print(walk(root))
# リストの順を [node.key] + walk(node.left) + walk(node.right) に変えて試しましょう。
scope.c の変数名を、辞書順に並べる
grep -o "int [a-z]*" ~/compiler/scope.c | sortここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
木の形で、探す手間が決まる
探すとき、根から1段ずつ下りて、比べます。比べる回数は、木の高さまでです。
小さい順に入れ続けると、木は右にだけ伸びて、一本の線になります。これは連結リストと同じで、探す手間は減りません。左右が釣り合うほど、木は低くなります。
例: 7個を入れる順番と高さ
| 入れる順 | 木の形 | 高さ | 比べる回数の最大 |
|---|---|---|---|
| 1, 2, 3, 4, 5, 6, 7 | 右にだけ伸びる一本の線 | 7 | 7 |
| 4, 2, 6, 1, 3, 5, 7 | 左右が同じ高さ | 3 | 3 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
二分探索木は、いつも速く探せると思いがちです。小さい順に入れると、一本の線になり、1つずつ調べるのと変わりません。速さは、木が低いときだけのものです。