Pythonの標準マップ型をエミュレートした内部が2分木のdictもどきを実装してみる

この記事は

• Pythonの標準マップ型(現在ではdictのみ)に準拠するのに必要な要素をまとめた
• 例として2分探索木で実装した

はじめに

Pythonでは標準マップ型としてdictのみがある．これはデータ構造としてはhashで実装されている． キーからオブジェクトへのマップを表現できるデータ構造としてhash以外に探索木を用いたものが知られているがPythonの標準ライブラリには存在しない(c++では2分木のstd::mapとハッシュ実装のstd::unordered_mapがある)．標準マップ型として必要な要素をまとめるとともに簡単な2分探索木を実装してみた．

マッピング型として必要な要素

• d[x]でアクセス: obj.__getitem__(key)
• d[x] = y で要素追加: obj.__setitem__(key, item)
• for k in d: ループでキーをイテレートする: obj.__iter__()
• x in dでキーが存在するかチェック: obj.__contains__(key)
• del d[x]でキーxを削除: obj.__delitem__(key)
• obj.keys(), obj.item(), obj.values でそれぞれキー， 要素， キーと要素のタプルのビューオブジェクトを返す(ここの実装では直接iteratorを返す)
• ビューオブジェクトは len(view_object), iter(view_object), x in view_objectをサポートしなければならない
• len(d)で要素数を返す: obj.__len__()
• キーがimmutableかどうか： ここでは未実装
• clear, get, pop, popitem, setdefault, update 等のメソッドの実装

実装

import queue
    
class BinaryTree(object):
    class Node(object):
        def __init__(self, _key=None, _item=None):
            self.key = _key
            self.item = _item
            self.left = None
            self.right = None
            
        def __repr__(self):
            return str(self.key)+': '+str(self.item)
        
        def __str__(self):
            return self.__repr__()
            
    def __init__(self, *args, **kargs):
        self.size = 0
        self.head = None
        if len(args):
            for key, item in args:
                self.insert(key, item)
        elif len(kargs):
            for key in kargs:
                self.insert(key, kargs[key])

    def search(self, key):
        return self._search(key, self.head, self.head)[0]

    def _search(self, key, node, parent):
        if not node:
            return None, parent
        
        if key == node.key :
            return node, parent
        elif key < node.key:
            return self._search(key, node.left, node)
        else:
            return self._search(key, node.right, node)

    def insert(self, key, item):
        if not self.head:
            self.head = self.Node(key, item)
            self.size += 1
            return
        n, p = self._search(key, self.head, self.head)
        if n:
            n.item = item
        else:
            self.size += 1
            if key < p.key:
                p.left = self.Node(key, item)
            else:
                p.right = self.Node(key, item)                    

    def delete(self, key):
        n, p = self._search(key, self.head, self.head)
        if n == p:
            self.head = None
            self.size -= 1
        else:
            self._delete(key, n, p)

    def _delete(self, key, node, parent):
        if node:
            if not node.left and not node.right:
                if parent.left == node:
                    parent.left = None
                else:
                    parent.right = None
                del node
                self.size -= 1                
            elif node.left and node.right:
                if parent.left == node:
                    right_min, right_min_parent = self.min_key_node(node.right, node)
                    node.key = right_min.key
                    node.item = right_min.item
                    self._delete(node.key, right_min, right_min_parent)
                else:
                    left_max, left_max_parent = self.max_key_node(node.left, node)
                    node.key = left_max.key
                    node.item = left_max.item
                    self._delete(node.key, left_max, left_max_parent)

            elif node.left:
                if parent.left == node:
                    parent.left = node.left
                else:
                    parent.right = node.left
                del node
                self.size -= 1                
            else:
                if parent.left == node:
                    parent.left = node.right
                else:
                    parent.right = node.right
                del node
                self.size -= 1
        
    def min_key_node(self, node, parent):
        if not node.left:
            return node, parent
        else:
            return self.min_key_node(node.left, node)
        
    def max_key_node(self, node, parent):
        if not node.right:
            return node, parent
        else:
            return self.max_key_node(node.right, node)

    def in_order_traverse(self, use_keys=True, use_items=True):
        if self.head:
            yield from self._in_order_traverse(self.head, use_keys, use_items)

    def _in_order_traverse(self, node, use_keys, use_items):
        if node.left:
            yield from self._in_order_traverse(node.left, use_keys, use_items)
        if use_keys and use_items:
            yield node.key, node.item
        elif use_keys:
            yield node.key
        else:
            yield node.item            
        if node.right:
            yield from self._in_order_traverse(node.right, use_keys, use_items)

    def clear(self):
        while self.head:
            self._delete(self.head.key)

    def copy(self):
        return BinaryTree(self.items())

    def get(self, key, default=None):
        n = self.search(key)
        if n:
            return n.item
        else:
            return default

    def pop(self, key):
        n = self.search(key)
        if n:
            i = n.item
            self.delete(key)
            return i
        else:
            self.__missing__(key)

        
    def __getitem__(self, key):
        n = self.search(key)
        if n:
            return n.item
        else:
            self.__missing__(key)

    def __missing__(self, key):
        raise KeyError(key)

    def __setitem__(self, key, item):
        return self.insert(key, item)

    def __delitem__(self, key):
        return self.delete(key)

    def __iter__(self):
        return self.in_order_traverse(use_keys=True, use_items=False)                        

    def __reversed__(self):
        return BinaryTreeIter(self.head, reverse=True)        
    
    def __contains__(self, key):
        if self.search(self.head):
            return True
        else:
            return False

    def __len__(self):
        return self.size

    def items(self):
        return self.in_order_traverse()        
    
    def keys(self):
        return self.in_order_traverse(use_keys=True, use_items=False)                
    
    def values(self):
        return self.in_order_traverse(use_keys=False, use_items=True)                        

    def __repr__(self):
        out = []
        for key, item in self.items():
            out.append(str(key)+': '+str(item))
        return '{'+', '.join(out)+'}'

    def __str__(self):
        return self.__repr__()

使用例

>>> import random
>>> bt = BinaryTree()
>>> random_data = list(range(20))
>>> random.shuffle(random_data)
>>> for k in random_data:
        bt[k] += k**2
>>> bt[10] = -1
>>> for k in bt:
        print('key:', k, 'value:', bt[k], end=', ')
key: 0 value: 0, key: 1 value: 1, key: 2 value: 4, key: 3 value: 9, key: 4 value: 16, key: 5 value: 25, key: 6 value: 36, key: 7 value: 49, key: 8 value: 64, key: 9 value: 81, key: 10 value: -1, key: 11 value: 121, key: 12 value: 144, key: 13 value: 169, key: 14 value: 196, key: 15 value: 225, key: 16 value: 256, key: 17 value: 289, key: 18 value: 324, key: 19 value: 361, 
>>> bt[100]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/Volumes/Macintosh_HD/Users/user/std_tree.py", line 178, in __getitem__
    self.__missing__(key)
  File "/Volumes/Macintosh_HD/Users/user/std_tree.py", line 181, in __missing__
    raise KeyError(key)
KeyError: 100

2分木なのでキーがソートされた順序で返るようにできました．

まとめ

現状の問題等

• d.pop(k,[d])dがなくkが存在しないキーのときKeyErrorをかえし， dがありkが存在しないときdをかえす． という挙動をどのように実装すればよいのか?(キーワード引数ではない) -> 引数を*argsで受けて自分で処理すればできる
• dict(ハッシュテーブル)の場合はhash値でkeyが同一かどうかで処理できる．しかし現状のようにツリーにするとkey同士の大小関係が定義されている必要がある． これはhasableなものならなんでもkeyにできるdictに対して制限が強く使いずらい．
• 上記を解決する手段としてkeyとしてhash値を使い， hash値の衝突に対応するために各nodeに複数のitemを格納可能とする方法はある． hash値をkeyとして使った場合かたよりがないかなどは不明
• 自前で探索木を構築する必要があるような場合は， 特殊な木の操作，検索時にノードを返す，途中のノードを保持する，サブツリーに対して処理するなどの個別的な場合であると考えられるので標準的なインターフェースで対応しきれず，また対応するのは不適切かもしれない

さいごに

とりあえずやってみたという感じです．こまごましたメソッドに関してはほとんどチェックしていないので申し訳ありません．また実装に関してもいろいろどうするのがベストプラクティスかわからないのでご指摘等頂ければ幸いです．