さわって覚える Python で二分探索木

2018/08/16
絶賛書き換え中...
コードは書き終えています。
6_2_binary_search_tree.py






f:id:domodomodomo:20171119172218p:plain


2分探索木とは、「「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。Wkipedia」だ、そうです。
2分探索木, Binary Search Tree - Wikipedia

Python で二分探索木を書きました。insert, delete, list を実装しています。また木を表示する Debug.log という関数を用意しました。
6_2_binary_search_tree.py


from binary_search_tree import *

# 上の図と同じ木を作る。
bst = BinarySearchTree()
bst.insert(8)
bst.insert(3)
bst.insert(1)
bst.insert(6)
bst.insert(10)
bst.insert(4)
bst.insert(7)
bst.insert(14)
bst.insert(13)
print(Debug.log(bst))
#              08              
#      03              10      
#  01      06              14  
#        04  07          13


# 8, 7 を削除する。
# 削除には2種類方法があります。
#     delete_left  ... 左の子の最大値をルートに持ってくる
#     delete_right ... 右の子の最小値をルートに持ってくる
bst.delete_left(8)
print(Debug.log(bst))
#              07              
#      03              10      
#  01      06              14  
#        04              13


bst.delete_right(7)
print(Debug.log(bst))
#              10              
#      03              14      
#  01      06      13
#        04   


# リストを表示する。
print(bst.list())
print(bst.list_sequentially())


# Debug.register_printer を実行した後は
# insert, delete_left, delete_right の度に
# 木が表示されます。
Debug.register_printer()
bst.insert(2)
#               10              
#       03              14      
#   01      06      13          
#     02  04        


◯ 参考にした神のサイト

delete の実装に当たって、次のサイトを参考にしました。 削除した木のルートを返すと色々と上手くいくことを学びました。
Algorithms with Python - 二分木 (binary tree) とヒープ (heap)

実装したクラスとメソッド

1. BinarySearchTree

木が 空 であった場合の対応を実装します。実際の処理は、root 属性に代入された BinarySearchNode クラスのオブジェクトに記述されています。

  1. insert(value)
    値を木に挿入します。

  2. search(value)
    値を木から検索します。ノードがあれば当該ノードを返します。ノードがなければ ValueError を返します。

  3. list()
    木をソートされたリストにします。

  4. list_sequentially()
    木をソートされたリストにします。再帰ではない方法で実装しています。これはイテレータを説明するためのものです。

  5. delete_left(value)
    値を木から削除します。 削除対象の値を持つノードの左側の木の中で最大値を持つノードを切り取り、削除された箇所に再結合します。

  6. delete_right(value)
    値を木から削除します。 削除対象の値を持つノードの右側の木の中で最小値を持つノードを切り取り、削除された箇所に再結合します。

2. BinarySearchNode

3. Route

要素を1つ1つ辿るためのイテレータです。

4. Test

5. Debug

木を表示する Debug.log という関数を用意しました。 この関数には、次の2つの制限があります。

  1. 0 ~ 99 の int 型
  2. 深さ 6 ~ 7

実装の方針

よく見かけるサンプルコードには、Tree と Node を実装しているものと Node だけ実装しているもの。 あるいは親への参照を保持する属性 parent を持っているものといないものがあります。

1. BinarySearchTree クラスと BinarySearchNode クラスの2つに分けるか、それとも分けないか。


BinarySearchTree クラスと BinarySearchNode クラス を分けるのは実装が面倒です。 しかし delete 削除の機能を実装する場合には、実装する必要があります。

1.1. ルートを削除したときの対応のため。
from binary_search_tree import *

# BinsarySearchNode を木に見立てる...
tree = BinarySearchNode(8)
tree.insert(3)
tree.insert(1)
tree.insert(6)
tree.insert(10)
tree.insert(4)
tree.insert(7)
tree.insert(14)
tree.insert(13)

# あるオブジェクトに tree を登録する。
dct = {'tree': tree}
print(Debug.log_node(dct['tree']))
"""
              08              
      03              10      
  01      06              14  
        04  07          13    
"""

# 8 を削除すると...
tree.delete_left(8)

# 8 しか表示されない...
print(Debug.log_node(dct['tree']))
"""
08
"""
1.2. 木が1つも値を持っていないときの対応のため

もし BinarySearchTree クラスと BinarySearchNode クラスをわけなかった場合、どうやって要素を持たない木を表現しますか? それには2つのやり方があると思います。

代替案 1: None
1つ目は None を値を持たない木であるとすることです。しかしそうすると、1度、木が空に None になってしまうと、もう木ではなくなってしまいます。結果的に insert, list と言った処理が実行できなくなります。

from binary_search_tree import *

# 木を生成する。
tree = BinarySearchNode(8)
tree.insert(3)
tree.insert(1)
tree.insert(6)
tree.insert(10)
tree.insert(4)
tree.insert(7)
tree.insert(14)
tree.insert(13)

# 木を空にする。
tree = tree.delete_left(8)
tree = tree.delete_left(3)
tree = tree.delete_left(1)
tree = tree.delete_left(6)
tree = tree.delete_left(10)
tree = tree.delete_left(4)
tree = tree.delete_left(7)
tree = tree.delete_left(14)
tree = tree.delete_left(13)

# 木を空にすると None になる
assert tree is None

# もう insert はできない...
# AttributeError
tree.insert(3)


代替案 2: BinarySearchNode(None)
2つ目は None を値に持つ BinarySearchNode を空の木と見立てることです。これなら空になっても insert などの処理は実行できそうです。 しかし結局 1.1 の問題が解決しないので採用しませんでした。

また、もし BinarySearchNode と BinarySearchTree を個別に実装するなら、 代替案 2 よりも 代替案 1 の方が、簡潔に実装できるので、BinarySearchNode としては 代替案 1 を採用しました。

2. BinarySearchNode の属性に parent を持たせる、それとも持たせない?

delete の処理が複雑になるからです。 特に parent の取り扱いで処理が、とても長くなってパッと見ではわかりづらいコードになります。

# parent を持たせると delete の処理が長くなっていまう。
class BinarySearchNode(object):
    
    ....
    
    def delete_left(self, value):
        if value < self.value:
            if self.left:
                self.left = self.left.delete_left(value)
            else:
                raise ValueError
        elif value > self.value:
            if self.right:
                self.right = self.right.delete_left(value)
            else:
                raise ValueError
        elif value == self.value:
            old_self = self
            if old_self.left:
                self = old_self.left.search_max()
                # self.left
                if self.left:
                    self.left.parent = self.parent
                # self
                self.parent = old_self.parent
                self.left = old_self.left.delete_max()
                # self
                if self.left:
                    self.left.parent = self
                self.right = old_self.right
                # self
                if self.right:
                    self.right.parent = self
            else:
                self = old_self.right
                # self
                if self:
                    self.parent = old_self.parent
            # old_self
            old_self.parent = None
            old_self.left = None
            old_self.right = None
        return self


list_sequential メソッドで parent があるとわかりやすくなるのですが、 list_sequential メソッドは二分探索木の処理を説明するためだけのメソッドで、本来は不要なので parent を持たせない実装にしました。

3. 再帰処理か while 文か?

再帰処理で処理しました。ただし list_sequentially に関わる処理を除きます。

特に深い理由がある訳ではありません。 イテレータに関わる処理は while 文でないとかけないので、それとの対比の意味で、基本的には再帰処理で記述しました。

実は quick sort と binary search で、二分探索木と全く同じことができます。

1. 二分探索 bisect

二分探索木には、どのような利点があるのでしょうか?

二分探索木は、二分木に対して、あるルールを適用することによって、データの探索効率を向上させたデータ構造です。
二分探索木 - Programming Place Plus アルゴリズムとデータ構造編


実は、わざわざ二分探索木を実装しなくても、ソートされたリストを用いて同じことができます。この方法を二分探索と言います。
二分探索 - わくわくアカデミー(鬼のようにわかりやすい)
二分探索 - Wikipedia

実は Python では二分探索を行う bisect と言う組み込みモジュールを提供してくれています。

random_list = [8, 3, 1, 6, 10, 4, 7, 14, 13]

sorted_list = sorted(random_list)
print(sorted_list)
# [1, 3, 4, 6, 7, 8, 10, 13, 14]


"""
1. bisect 
  ソートされた順番を崩すことなく
  要素を挿入できる。
"""
import bisect
bisect.insort_left(sorted_list, 11)
print(sorted_list)
# [1, 3, 4, 6, 7, 8, 10, 11, 13, 14]


"""
2. 二分探索木
  ソートされた順番を崩すことなく
  要素を挿入できる、と考えることもできる。
"""
binary_search_tree = BinarySearchTree()
binary_search_tree.insert_iterable(random_list)
binary_search_tree.insert(11)
print(list(binary_search_tree))
# [1, 3, 4, 6, 7, 8, 10, 11, 13, 14]

8.6. bisect 配列二分法アルゴリズム - Python 標準ライブラリ

2. クイックソート

二分探索木を使ったソートは、基本的にはクイックソートと同じことをしています。
クイックソート - わくわくアカデミー(鬼のようにわかりやすい)

クイックソートは、基準になる値を1つ決め、それより大きい値のグループと小さい値のグループに分けます。そしてこの作業を繰り返し、ソートされたリストを得ます。それは、ちょうど二分探索木が、挿入された要素を左側の子と右側の子に振り分ける動作と、とてもよく似ています。

実際、クイックソートのコードは、二分探索木からリストを生成するコードとそっくりです。

def quick_sort(lst):
    if not lst:
        return []
    
    # 1.
    smaller_sorted_list = quick_sort([e for e in lst[1:] if e <= lst[0]])
    center = lst[0]
    bigger_sorted_list = quick_sort([e for e in lst[1:] if e > lst[0]])
    # 2.
    sorted_list = smaller_sorted_list + [center] + bigger_sorted_list
    # 3.
    return sorted_list


lst = [8, 3, 1, 6, 10, 4, 7, 14, 13]
print(quick_sort(lst))

イテレータの実装の方針(Path クラス)

1...全部、リストを使う却下
2...一部、リストを使う採用
3...一切、リストを使わない却下

1. 却下 全部リストを使う
リストに全部保存してしまう

どうやってイテレータを実装しましょう?せっかく、リストを作ってくれるメソッド generate_sorted_list があるので、一度リストを生成して iter 関数でリストのイテレータを借用する方法も考えられます。

この実装は、木が大きかった時に問題になります。なぜなら、イテレータを生成する時に、木の要素を全てメモリに確保するために、たくさんのメモリを必要とするからです。この実装は 7 章で作ったコピーによるイテレータと同じような実装になってしまっています。

    def __iter__(self):
        # 2分探索木からリストを生成して、
        lst = self.generate_sorted_list()
        # そのリストのイテレータを返すようにする。
        return iter(lst)

2. 採用 少しだけリストを使う
根から現在位置への経路をリストに保存する

generate_sorted_list メソッドは、再帰呼び出しで書かれているので、ほとんどのコードを next メソッドに使えません。next メソッドは generate_sorted_list メソッドを再帰呼び出しではない形で書き換えました。

class BinarySearchTreeIterator(object):
    def __next__(self):
        # 現在位置から見て、右下に子がいれば木を降下 _down
        if self._current_node().right is not None:
            self._down()
        # 現在位置から見て、右下に子がいなければ木を上昇 _up
        else:
            self._up()
        return self._current_node().element


基本的な考え方は、リストのコピーでないイテレータが要素の現在位置を self.index に保存していたのと同じように、要素の現在位置を保存させたいと考えています。

しかし、どうしても探索中に経路を戻る必要があるので、要素の現在位置だけではダメで、根からの要素の現在位置への経路が必要になります。そこで経路をリスト self._route を使って保存しています。反対に generate_sorted_list 関数は、根からの現在位置の要素への経路を 再帰呼び出しのスタック を使って保存しています。

class Path(object):
    
    ...

    def _seek_right_min(self):
        self._route.append(self._current_node().right)
        while self._current_node().left:
            self._route.append(self._current_node().left)


3. 却下 一切リストを使わない
現在位置だけを保存する

2 のやり方は、根から現在の要素までの経路をリスト self._route に保存してしています。経路の分だけメモリを消費しています。2 のやり方は、リストに要素を全ての保存するよりは、メモリの消費量は、幾らか良い実装になっています。

では、完全に self._route リストを使わないようにするにはどうすれば良いでしょうか?BinarySearchTree そのものを修正すればできます。その方がメモリの使用量はさらに若干改善され、おそらく速度も 2 よりは若干速くなると思います。Python では思い操作である属性参照や関数呼び出しの回数が少なくなると思うからです。

しかし、今回は、木クラスとイテレータクラスの役割を完全に分離した実装にしました。これは、イテレータの役割を際立たせて、イテレータを理解しやすくするためです。また、責任を分担するという可読性においても、こちらの方が望ましいかなと思ったりもします。

イテレータを実装したら list を生成するメソッドを実装しない。

iterable にした場合、 list を取得するときは、generate_sorted_list のような list を生成するメソッドは、もう必要ありません。なぜなら list のコンストラクタを用いて、list が得られるからです。

>>> tree = BinarySearchTree()
>>> tree.insert_iterable((1, 2, 3, 4, 5, 6))
>>>
>>> # OK
>>> list(tree)
[1, 2, 3, 4, 5, 6]
>>>
>>> # NG 実装しない。
>>> # tree.generate_sorted_list()
>>>