二叉查找树

什么是二叉查找树？

二叉查找树又名二叉排序树、二叉搜索树，具有如下性质：

1. 若左子树不为空，则左子树上的所有节点的值均小于它的根节点上的值
2. 若右子树不为空，则右子树上的所有节点的值均大于它的根节点上的值
3. 左、右子树也分别都为二叉查找树
4. 没有键值相等的两个节点

二叉查找树的优缺点

1. 查找性能
查找过程：从根节点出发，若根节点的关键字等于要查找的值，则查找完成；如果小于根节点的值，则递归查找左子树；否则递归查找右子树。如果到叶子节点，还没有查找到，则说明这个树中没有这个值。

• 当二叉树中每个节点左右子树的高度大致相同，则树的高度为logN。则平均时间复杂度也就为O(logN)
• 当二叉树插入节点时，关键字本来就有序，二叉树就会形成一个单支树结构，查找也就变得和顺序查找一模一样了。这时的查找效率最低为0(n)

2. 插入性能
因为新节点插入到树中的叶子节点上的，所以插入一个节点和查找一个不存在的值的代价是一样的。

3. 删除性能
首先找到这个要删除的节点p，代价和查找这个值一样。然后需要改变树的结构。如果左右子树都为空，则直接删除这个叶子节点；

1.png

如果这个删除节点的左右子树只存在一个，那么直接把左节点或右节点的父亲设置为p的父亲即可；

2.png

如果左右子树都存在，则把右子树中值最小的节点找到，交换到要删除节点的位置，然后调整下子树即可。

3.png

python实现二叉查找树

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

class BinarySearchTree(object):
    # 每个节点的结构，left和right的值代表左右子节点，value为当前节点关键字的值
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    # 插入一个节点
    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

    # 关键值最小的节点
    def findMin(self):
        if self.left:
            return self.left.findMin()
        else:
            return self

    # 关键值最大的节点
    def findMax(self):
        if self.right:
            return self.right.findMax()
        else:
            return self

    # 删除一个节点
    def delete(self, x):
        node, parent = self.find(x);
        # 如果有这个值才进行删除操作
        if node is not None:
            # 如果该节点下没有子节点
            if not node.left and not node.right:
                if parent.left is node:
                    parent.left = None
                else:
                    parent.right = None
                del node
            # 只有一个子节点时，则让这个子节点替换这个要删除的节点
            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
            # 删除节点有左子节点，也有右子节点。
            else:
                parent = node
                successor = node.right
                while successor.left:
                    parent = successor
                    successor = successor.left
                # 找到右子树中最小的值后赋值给要删除的节点
                node.value = successor.value
                # 左右子树微调
                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()

执行结果

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