二叉树是每个节点最多只能有2个子节点的树状结构.

二叉搜索树在二叉树的基础上增加了一个条件:设x是二叉搜索树中的一个结点.如果y是x左子树中的一个结点,那么y.key \leq x.key.如果y是x右子树中的一个结点,那么y.key \geq x.key.

通俗将就是左子树的数据比右子树的数据小.但是要注意,上面的数据有可能比下面数据小也有可能比下面结点数据大.
image.png

数据查找

数据查找过程从树根开始,每遇到一个节点x,比较关键字k与x.key,如果两个关键字相等,查找结束,如果k小于x.key,则在x的左子树继续查找,因为二叉搜索树的性质蕴含了k不可能被存储在右子树中.对称的,如果k大于x.key则在右子树中继续查找.

image.png

查找过程是一个简单的路径,所以运行时间为O(h),其中h是这棵树的高度.

def tree_search(x, k):
    while x != None and k != x.key:
        if k < x.key:
            x = x.left
        else:
            x = x.right
    return x

最大关键字元素和最小关键字元素

寻找最大关键字元素或是最小关键字元素在二叉搜索树里真的非常的简单,只要不停的找右子树或左子树就可以了.

def tree_minimum(x):
    while x.left != None:
        x = x.left
    return x

def tree_maximum(x):
    while x.right != None:
        x = x.right
    return x

后继和前驱

节点x的后继是大于x.key的最小关键字的节点.节点x的前驱是小于x.key的最大关键字的节点.

寻找x的后继有2种情况:

  • x有右子树,那么只需要在右子树中找最小关键字元素就是x的后继
  • x没有右子树,那么x的后继是x的一个有左孩子的最底层祖先,并且x在其左子树中,例如上图中13节点的后继是15节点

数据插入

插入数据很简单,本着小就找左子树,大就找右子树的原则,循环找下去,直到找到一个"空位",然后插入就可以了.

def tree_insert(T,z):
    y = None
    x = T
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if z.key < y.key:
        y.left = z
    else:
        y.right = z

数据删除

删除节点z可以分为三种情况,只有一种情况比较棘手:

  • 如果z没有子节点,之间将这个节点删掉就好了
  • 如果z有一个子节点,需要将子节点替换到z的位置
  • 如果z有两个子节点,并且z的后继y(一定在z的右子树中)是z的右孩子,用y替换z.
  • 如果z有两个子节点,并且z的后继y(一定在z的右子树中)是z的右子树中的节点,先用y的有孩子替换y,然后在用y替换z.

image.png

posted @ 2019-02-10 13:15:03
评论加载中...

发表评论