什么是二叉查找樹？

二叉查找樹又名二叉排序樹、二叉搜索樹，具有如下性質(zhì)：

1. 若左子樹不為空，則左子樹上的所有節(jié)點的值均小于它的根節(jié)點上的值
2. 若右子樹不為空，則右子樹上的所有節(jié)點的值均大于它的根節(jié)點上的值
3. 左、右子樹也分別都為二叉查找樹
4. 沒有鍵值相等的兩個節(jié)點

二叉查找樹的優(yōu)缺點

1. 查找性能
查找過程：從根節(jié)點出發(fā)，若根節(jié)點的關(guān)鍵字等于要查找的值，則查找完成；如果小于根節(jié)點的值，則遞歸查找左子樹；否則遞歸查找右子樹。如果到葉子節(jié)點，還沒有查找到，則說明這個樹中沒有這個值。

• 當二叉樹中每個節(jié)點左右子樹的高度大致相同，則樹的高度為logN。則平均時間復雜度也就為O(logN)
• 當二叉樹插入節(jié)點時，關(guān)鍵字本來就有序，二叉樹就會形成一個單支樹結(jié)構(gòu)，查找也就變得和順序查找一模一樣了。這時的查找效率最低為0(n)

2. 插入性能
因為新節(jié)點插入到樹中的葉子節(jié)點上的，所以插入一個節(jié)點和查找一個不存在的值的代價是一樣的。

3. 刪除性能
首先找到這個要刪除的節(jié)點p，代價和查找這個值一樣。然后需要改變樹的結(jié)構(gòu)。如果左右子樹都為空，則直接刪除這個葉子節(jié)點；

1.png

如果這個刪除節(jié)點的左右子樹只存在一個，那么直接把左節(jié)點或右節(jié)點的父親設(shè)置為p的父親即可；

2.png

如果左右子樹都存在，則把右子樹中值最小的節(jié)點找到，交換到要刪除節(jié)點的位置，然后調(diào)整下子樹即可。

3.png

python實現(xiàn)二叉查找樹

#!/usr/bin/python
# encoding: utf-8

class BinarySearchTree(object):
    # 每個節(jié)點的結(jié)構(gòu)，left和right的值代表左右子節(jié)點，value為當前節(jié)點關(guān)鍵字的值
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    # 插入一個節(jié)點
    def insert(self, x):
        if x < self.value:
            if self.left:
                self.left.insert(x)
            else:
                self.left = BinarySearchTree(x)
        elif x > self.value:
            if self.right:
                self.right.insert(x)
            else:
                self.right = BinarySearchTree(x)

    # 遍歷二叉樹查找一個值
    def find(self, x, parent=None):
        if x == self.value:
            return self, parent
        elif x < self.value and self.left:
            return self.left.find(x, self)
        elif x > self.value and self.right:
            return self.right.find(x, self)
        else:
            return None, None

    # 關(guān)鍵值最小的節(jié)點
    def findMin(self):
        if self.left:
            return self.left.findMin()
        else:
            return self

    # 關(guān)鍵值最大的節(jié)點
    def findMax(self):
        if self.right:
            return self.right.findMax()
        else:
            return self

    # 刪除一個節(jié)點
    def delete(self, x):
        node, parent = self.find(x);
        # 如果有這個值才進行刪除操作
        if node is not None:
            # 如果該節(jié)點下沒有子節(jié)點
            if not node.left and not node.right:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            # 只有一個子節(jié)點時，則讓這個子節(jié)點替換這個要刪除的節(jié)點
            elif (not node.left and node.right) or (node.left and not node.right):
                if node.left:
                    n = node.left
                else:
                    n = node.right
                if parent:
                    if parent.left is node:
                        parent.left = n
                    else:
                        parent.right = n
                del node
            # 刪除節(jié)點有左子節(jié)點，也有右子節(jié)點。
            else:
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                # 找到右子樹中最小的值后賦值給要刪除的節(jié)點
                node.value = successor.value
                # 左右子樹微調(diào)
                if parent.left == successor:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                del successor

    # 按照順序打印
    def printTree(self):
        if self.left:
            self.left.printTree()
        print self.value,
        if self.right:
            self.right.printTree()


if __name__ == '__main__':
    root = BinarySearchTree(10)
    root.insert(6)
    root.insert(5)
    root.insert(8)
    root.insert(7)
    root.insert(9)
    root.printTree()
    print ''  # 另起一行
    x, y = root.find(9)
    print x.value, y.value  # 打印查explorer.exe找的值和其父親的值
    print root.findMax().value, root.findMin().value  # 打印最小值和最大值
    root.delete(5)
    root.printTree()

執(zhí)行結(jié)果

5 6 7 8 9 10 
9 8
10 5
6 7 8 9 10