IT工程師數位筆記本

二叉查找樹，英文Binary Search Tree，也叫二叉排序樹，是一種基本的數據結構，簡稱BST

它支持多種動態集合操作，包括查找（find），最小值（minimum），最大值（maximum），后繼（successor），前驅（predecessor），插入（insert），刪除（delete），以及中序遍歷等。它既可以用作字典，也可以用作優先隊列。

BST不是穩定的樹，極端情況下會退化為線性結構，但平均期望上，insert，delete操作可以為O(lg n),樹的期望高度為O（lg n）。

參考了《算法導論》等書，寫出了具有insert，delete，find功能的BST，如果有認為不正確的地方歡迎拍磚。

#coding:utf8
#author:HaxtraZ


class BST(object):
    """二叉查找樹的簡單實現"""
    def __init__(self):
        self.root = None

    def insert(self, val):
        newNode = BSTnode(val)
        if self.root is None:
            self.root = newNode
        else:
            curNode = self.root
            while True:
                if val < curNode.val:
                    #進入左子樹
                    if curNode.left is None:
                        curNode.left = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.left
                else:
                    #進入右子樹
                    if curNode.right is None:
                        curNode.right = newNode
                        newNode.parent = curNode
                        break
                    curNode = curNode.right

    def find(self, val):
        curNode = self.root
        while curNode is not None:
            if val < curNode.val:
                curNode = curNode.left
            elif val > curNode.val:
                curNode = curNode.right
            else:
                return True  # 找到了！

        return False  # 沒找到

    def delete(self, val):
        curNode = self.root
        while curNode is not None:
            if val < curNode.val:
                curNode = curNode.left
            elif val > curNode.val:
                curNode = curNode.right
            else:
                # 找到了val
                if curNode.left is not None and curNode.right is not None:
                    target = self.successor(curNode.right).val
                    curNode.val = target.val
                    self.delete(target)
                elif curNode.left is not None:
                    if curNode == self.root:
                        self.root = curNode.left
                    parNode = curNode.parent
                    subNode = curNode.left
                    if parNode.left == curNode:
                        parNode.left = subNode
                    else:
                        parNode.right = subNode
                    subNode.parent = parNode
                else:
                    if curNode == self.root:
                        self.root = curNode.right
                    parNode = curNode.parent
                    subNode = curNode.right
                    if parNode.right == curNode:
                        parNode.right = subNode
                    else:
                        parNode.left = subNode

                return True
        return False  # 不存在val，刪除失敗

    def minimum(self, node):
        # 返回最小值的節點。其實就是most left one
        curNode = node
        if curNode is None:
            #空樹
            return None
        while curNode.left is not None:
            curNode = curNode.left
        return curNode

    def maximum(self, node):
        #返回最大值的節點。其實就是most right one
        curNode = node
        if curNode is None:
            #空樹
            return None
        while curNode.right is not None:
            curNode = curNode.right
        return curNode

    def successor(self, node):
        #node是二叉查找樹中的一個節點
        #尋找node的后繼節點，然后返回
        curNode = node
        if curNode.right is not None:
            #右子樹非空，返回右子樹最左節點
            return self.minimun(curNode.right)
        else:
            #右子樹為空，則返回“最低祖先”
            parNode = curNode.parent
            while parNode is not None and parNode.right == curNode:
                curNode = parNode
                parNode = parNode.parent
            return parNode

    def show(self):
        # 中序遍歷
        self.display(self.root)
        print '\n'

    def display(self, node):
        if node is None:
            return
        self.display(node.left)
        print node.val,
        self.display(node.right)

#    def predecessor(self, node):
        # 獲取前驅節點。類似于獲取后繼節點，這里省略。。


class BSTnode(object):
    """二叉查找樹的節點類型"""
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


if __name__ == '__main__':
    mylist = [2, 2, 7, 4, 1, 5]
    bst = BST()
    for i in range(len(mylist)):
        bst.insert(mylist[i])

    bst.show()
    bst.delete(7)
    bst.show()