二分探索木 - みずぴー日記

30分プログラム、その206。二分探索木を作る。
そういえば、二分探索木は30分プログラムで作ったことがなかったので。ただ、削除は面倒そうなので、また次回。
ツリーなので、Compositeパターンを多少意識してる。duck typingなので、インターフェースは不要だけど。

使い方

# ツリーを生成する
>>> tree = Branch(5)
>>> tree
(Branch 5 Leaf Leaf)

# ツリーにいくつか値を挿入する
>>> tree.insert_value(10)
(Branch 5 Leaf (Branch 10 Leaf Leaf))

>>> tree.insert_value(1)
(Branch 5 (Branch 1 Leaf Leaf) (Branch 10 Leaf Leaf))

# ツリーに含まれているかチェックする
>>> tree.contain(1)
True
>>> tree.contain(3)
False

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-
#
# binary_tree.py -
#
# Copyright(C) 2007 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2007/12/19 23:07:43
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

class Leaf:
    def __repr__(self):
        return "Leaf"

    def insert(self,node):
        return node

    def is_leaf(self):
        return True

    def contain(self,value):
        return False

class Branch:
    def __init__(self,value,left=Leaf(),right=Leaf()):
        self.value = value
        self.left = left
        self.right = right

    def __repr__(self):
        return "(Branch %s %s %s)" % (self.value,repr(self.left),repr(self.right))

    def insert_value(self,value):
        return self.insert(Branch(value))

    def insert(self,node):
        target = self.left if node.value < self.value else self.right

        if node.value < self.value:
            self.left = self.left.insert(node)
        else:
            self.right = self.right.insert(node)
        return self

    def is_leaf(self):
        return True

    def contain(self,value):
        if self.value == value:
            return True
        elif self.value < value:
            return self.right.contain(value)
        else:
            return self.left.contain(value)

参考

過去の30分プログラム