相关概念
- BST（Binary Search Tree），在树中的任一节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都要大于这个节点的值。
BST查找操作
- 先取根节点，如果它等于要查找的数据，那就返回；如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def bstFind(self, tree, val):
if not tree:
return None
while tree:
if tree.val < val:
tree = tree.right
elif tree.val > val:
tree = tree.left
else:
return tree
return None
BST的插入操作
- 类似于查找操作，需要从根节点开始，依次比较要插入的数据和节点的大小关系。如果要插入的数据比节点数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再遍历左子树，查找插入位置。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def bstInsert(self, tree, val):
if not tree:
tree = TreeNode(val)
return
while tree:
if tree.val < val:
if tree.right is None:
tree.right = TreeNode(val)
return
tree = tree.right
else:
if tree.left is None:
tree.left = TreeNode(val)
return
tree = tree.left
BST删除操作
- state1，如果要删除的节点没有子节点，只需直接将父节点中指向要删除节点的指针置为null。
- state2，如果要删除的节点中只有1个子节点，只需更新父节点中指向要删除节点的指针，让它指向要删除节点的子节点。
- state3，如果要删除的节点有2个子节点，需要找到这个节点的右子树中的最小节点（因为这个节点满足大于被删除节点左子树的所有节点，小于被删除节点右子树中除自身外的所有节点，它可以取代被删除节点的位置），把它替换到要删除的节点上，然后再删除掉这个右子树的最小节点，因为最小节点肯定没有左子树，所以可用state1或state2来进行这个删除操作。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def bstDelete(self, tree, val):
# 记录待删除节点的父节点
pp = None
while p and p.val != val:
pp = p
if val > p.val:
p = p.right
else:
p = p.left
# 没有找到要删除的节点
if p is None:
return
# 要删除的节点有2个子节点
if p.left and p.right:
min_p = p.right
min_pp = p
# 找右子树中最小节点，记录其父节点，待做删除操作
while min_p.left:
min_pp = min_p
min_p = min_p.left
# 这里的赋值是将现在右子树中最小节点的值给要删除的节点，这个值给过来之后，
# 就相当于删除了p节点了，并不动p节点的左右节点
p.val = min_p.val
# 对于state3，此时已经删除了p节点，还需要删除右子树中最小的节点，
# 此时将变量p作为右子树中最小节点的引用，转换为state1或state2
p = min_p
pp = min_pp
# 删除min_p或者删除只有1个子节点的节点
child = None
if p.left:
child = p.left
elif p.right:
child = p.right
else:
child = None
# 删除根节点，且根节点只有一个子节点
if not pp:
tree = child
elif pp.left is p:
pp.left = child
else:
pp.right = child
BST的其他特性
- 中序遍历BST，可以输出有序的数据序列，时间复杂度是O(n)，因此，BST也叫二叉排序树。
BST的两种存储形式
-
链式存储法：
每个节点有3个字段，一个存储数据，另外两个是指向左右子节点的指针，只要拎住根节点，就能通过左右子节点的指针，把整棵树都串起来。大部分二叉树代码都是通过这种结构实现的。 -
顺序存储法：（基于数组）
如果节点X存储在数组下标为i的位置，那么下标为2*i的位置存储的就是左子节点，下标为2*i+1的位置存储的就是右子节点。反过来，下标为i//2的位置存储的就是它的父节点。通过这种方式，我们只要知道根节点存储的位置（一般为了方便计算子节点，根节点会存储在下标为1的位置），这样就可以通过下标计算，把整棵树都串起来。
BST时间复杂度分析
- 最不理想情况
左右节点极度不均衡，退化成链表，时间复杂度变为O(n)。 - 最理想情况
一棵完全二叉树（或满二叉树）。此时时间复杂度和树的高度成正比O(height)，此时，问题转变为如何求一棵包含n个节点的完全二叉树的高度。
包含n个节点的满二叉树中，第一层包含1个节点，第二程包含2个节点，第三层4个...，第k层包含2^(k-1)个节点。
对于完全二叉树来说，最后一层节点个数在1个到2^(L-1)个之间（假设最大层数是L）。
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2^(L-2)+2^(L-1)
借助等比数列的求和公式，可算出L的范围是[log2(n+1), log2n+1]，完全二叉树的层数小于等于log2n+1，也就是说，完全二叉树的高度小于等于log2n。
当二叉树极度不平衡的时候，它的查找性能不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的平衡二叉查找树，它的高度接近logn，插入、操作、查找操作的时间复杂度也比较稳定，是O(logn)。
网友评论