BST树（Python实现）

BST树，又称为二叉排序树Binart Sort Tree
○ 若左子树不空，则左子树上所有结点的值均小于它的根结点的值
○ 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
○ 它的左右子树也为二叉排序树

实现代码

# coding:utf-8
class BinarySearchTree:
    def __init__(self):
        self.root = None
        self.size = 0
    def length(self):
        return self.size
    def __len__(self):
        return self.size
    def __setitem__(self, k, v):
        self.put(k, v)
    def __getitem__(self, key):
        return self.get(key)
    def __contains__(self, key):
        if self._get(key, self.root):
            return True
        else:
            return False
    def put(self, key, val):
        if self.root:
            self._put(key, val, self.root)
        # 空树
        else:
            self.root = TreeNode(key, val)
        self.size = self.size + 1
    def _put(self, key, val, currentNode):
        # 左子树
        if key < currentNode.key:
            if currentNode.hasLeftChild():
                self._put(key, val, currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key, val, parent=currentNode)
        # 右子树
        else:
            if currentNode.hasRightChild():
                self._put(key, val, currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key, val, parent=currentNode)
    def get(self, key):
        if self.root:
            res = self._get(key, self.root)
            if res:
                return res.payload
            else:
                return None
        else:
            return None
    def _get(self, key, currentNode):
        if not currentNode:
            return None
        elif currentNode.key == key:
            return currentNode
        elif key < currentNode.key:
            return self._get(key, currentNode.leftChild)
        else:
            return self._get(key, currentNode.rightChild)
class TreeNode:
    def __init__(self, key, val, left=None, right=None,
                 parent=None):
        self.key = key
        self.payload = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
    def hasLeftChild(self):
        return self.leftChild
    def hasRightChild(self):
        return self.rightChild
    def isLeftChild(self):
        return self.parent and self.parent.leftChild == self
    def isRightChild(self):
        return self.parent and self.parent.rightChild == self
    def isRoot(self):
        return not self.parent
    def isLeaf(self):
        return not (self.rightChild or self.leftChild)
    def hasAnyChildren(self):
        return self.rightChild or self.leftChild
    def hasBothChildren(self):
        return self.rightChild and self.leftChild
    def replaceNodeData(self, key, value, lc, rc):
        self.key = key
        self.payload = value
        self.leftChild = lc
        self.rightChild = rc
        if self.hasLeftChild():
            self.leftChild.parent = self
        if self.hasRightChild():
            self.rightChild.parent = self
if __name__ == '__main__':
    tree = BinarySearchTree()
    for k, v in zip(range(ord('a'), ord('a') + 10), [62, 58, 88, 47, 73, 99, 35, 51, 93, 37]):
        tree.put(v, chr(k))
    print tree[88]

复杂度

最坏复杂度为O(n),最好为O(1)