二叉查找树

作者: 心_的方向 | 来源:发表于2016-12-21 22:43 被阅读86次

什么是二叉查找树?

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

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

二叉查找树的优缺点

  1. 查找性能
    查找过程:从跟节点出发,若根节点的关键字等于要查找的值,则查找完成;如果小于根节点的值,则递归查找左子树;否则递归查找右子树。如果到叶子节点,还没有查找到,则说明这个树中没有这个值。
  • 当二叉树中每个节点左右子树的高度大致相同,则树的高度为 logN。则平均时间复杂度也就为 O(log N)
  • 当二叉树插入节点时,关键字本来就有序,二叉树就会形成一个单支树结构,查找也就变得和顺序查找查找一模一样了。这时的查找效率最低为 O(n)
  1. 插入性能
    因为新节点插入到树中的叶子节点上的,所以插入一个节点和查找一个不存在的值的代价是一样的为O(logN)。
  2. 删除性能
    首先找到这个要删除的节点p,代价和查找这个值一样的为O(logN)。然后需要改变数的结构。如果左右子树都为空,则直接删除这个叶子节点;


    来自网络.png

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


    来自网络.png
    如果左右子树都存在,则把右子树中值最小的节点找到,交换到要删除节点的位置,然后调整下子树即可。
    图片来自网络.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

相关文章

  • 极客时间数据结构与算法之美笔记25~26

    二叉树到二叉查找树,是为了查找数据的效率接近logN。 二叉查找树到平衡二叉查找树,是为了防止二叉查找树沦为链表。...

  • 二叉查找树

    1)二叉查找树是什么?2)二叉查找树的插入、删除、查找?3)Go代码实现 一、二叉查找树是什么?二叉查找树(BST...

  • 红黑树

    红黑树的本质就是一棵二叉查找树,所以先从二叉查找树来了解起。 二叉查找树 二叉查找树又称有序二叉树,具有以下特性:...

  • 二叉查找树

    二叉查找树,又称二叉搜索树 二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质: ...

  • 99-数据结构和算法

    难点:二叉树的遍历 红黑树 图的遍历 二叉查找树二叉查找树(binary search tree),二叉查找树在二...

  • 11-二叉查找树

    二叉查找树 1.什么是二叉查找树? 二叉查找树是一种支持数据动态的插入,删除,查找的数据结构。 2.二叉查找树的设...

  • 17张图带你解析红黑树的原理!保证你能看懂!

    二叉查找树 由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。 二叉查找树(Bin...

  • 二叉树 堆 2019-04-17

    二叉树 实现一个二叉查找树,并且支持插入、删除、查找操作 实现查找二叉查找树中某个节点的后继、前驱节点 实现二叉树...

  • 6. 二叉树创建-查找

    1. 递归方式实现二叉树的构建2. 树、二叉树、二叉查找树3. 二叉树排序树的理解4. 二叉查找树5. 二叉树的查找

  • 数据结构中的各种树

    一、二叉树 二、二叉查找树(又称二叉排序树,二叉搜索树) 二叉查找树(Binary Search Tree)它或者...

网友评论

    本文标题:二叉查找树

    本文链接:https://www.haomeiwen.com/subject/mjzfvttx.html