Python BTree 学习－广度优先搜索

不说别的见源码

#coding=utf-8
import sys, os
import bisect
import string


class Entity(object):
    """data entity"""
    __slots__ = ("key", "value",)

    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __str__(self):
        return self.key

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

    def __cmp__(self, key):
        if key > self.key:
            return 1
        elif key == self.key:
            return 0
        else:
            return -1


class Node(object):
    """B Node"""
    #__slots__ = ("parent", "entities", "childes",)

    def __init__(self):
        self.parent = None
        self.entities = []
        self.childes = []

    def find(self, key):
        i = bisect.bisect_left(self.entities, key)
        if i != len(self.entities) and self.entities[i].key == key:
            return self.entities[i].value

    def delete(self, key):
        """delete key"""
        i = bisect.bisect_left(self.entities, key)
        if i != len(self.entities) and self.entities[i].key == key:
            e = self.entities[i]
            del self.entities[i]
            return i, e
        else:
            return None, None


    def is_leaf(self):
        return len(self.childes) == 0

    def add_entity(self, entity):
        self.entities.append(entity)
        self.entities.sort(key=lambda x:x.key)

    def add_child(self, node):
        self.childes.append(node)
        node.parent = self
        self.childes.sort(key=lambda x:x.entities[0].key)


class BTree(object):
    def __init__(self, size=6):
        self.size = size
        self.root = None
        self.length = 0

    def add(self, key, value=None):
        self.length += 1

        if self.root:
            current = self.root
            while not current.is_leaf():
                for i, e in enumerate(current.entities):
                    if e.key > key:
                        current = current.childes[i]
                        break
                    elif e.key == key:
                        e.value = value
                        return
                else:
                    current = current.childes[-1]

            current.add_entity(Entity(key, value))

            if len(current.entities) > self.size:
                self._split_(current)
        else:
            #init root
            self.root = Node()
            self.root.add_entity(Entity(key, value))


    def _split_(self, node):
        """Rules
        1、middle index node become parent
        2、create right Nodes move parents right go to this node
        """
        middle = len(node.entities) / 2
        top = node.entities[middle]

        right = Node()
        for e in node.entities[middle + 1:]:
            right.add_entity(e)

        for n in node.childes[middle + 1:]:
            right.add_child(n)

        left = node
        left.entities = node.entities[:middle]
        left.childes = node.childes[:middle + 1]

        parent = node.parent
        if parent:
            parent.add_child(right)
            parent.add_entity(top)
            if len(parent.entities) > self.size:
                self._split_(parent)
        else:
            self.root = Node()
            self.root.add_entity(top)
            self.root.add_child(left)
            self.root.add_child(right)


    def get(self, key):
        e, v = self._find_node_(key)
        return v


    def _find_node_(self, key):
        if self.root:
            current = self.root
            while current.entities:
                bisect.bisect_left(current.entities, key)
                for i, e in enumerate(current.entities):
                    if e.key > key:
                        current = current.childes[i]
                        break
                    elif e.key == key:
                        return e, e.value
                else:
                    current = current.childes[-1]


    def delete(self, key):
        """#一般都标记删除不真删除"""
        pass


def bfs(root):
    """Iterator traverses a tree in breadth-first order."""
    queue = []
    queue.append(root)
    while len(queue) > 0:
        node = queue.pop(0)
        yield node
        for child in node.childes:
            queue.append(child)
    return


if __name__ == '__main__':
    t = BTree()
    for i in xrange(26):
        key = string.lowercase[i % 26]
        value = i
        t.add(key, value)
    root = t.root

    print "generate tree ......"
    for node in bfs(root):
        if node.parent:
            print "parent",
            for e in node.parent.entities:
                print e,
        print
        for e in node.entities:
            print e,
        print

    print
    print "test btree get"
    for i in xrange(26):
        key = string.lowercase[i % 26]
        print key, t.get(key), "-",