要实现一个高效的二叉搜索树(BST),可以使用AVL树或红黑树等自平衡二叉搜索树。这里以AVL树为例,给出插入、删除和查找操作的代码实现及时间复杂度分析。
首先,定义一个节点类:
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
接下来,实现AVL树的插入操作:
def insert(root, key):
if not root:
return TreeNode(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
if balance > 1:
if key < root.left.key:
return right_rotate(root)
else:
root.left = left_rotate(root.left)
return right_rotate(root)
if balance < -1:
if key > root.right.key:
return left_rotate(root)
else:
root.right = right_rotate(root.right)
return left_rotate(root)
return root
然后,实现AVL树的删除操作:
def delete(root, key):
if not root:
return root
if key < root.key:
root.left = delete(root.left, key)
elif key > root.key:
root.right = delete(root.right, key)
else:
if root.left is None:
temp = root.right
root = None
return temp
elif root.right is None:
temp = root.left
root = None
return temp
temp = get_min_value_node(root.right)
root.key = temp.key
root.right = delete(root.right, temp.key)
if root is None:
return root
root.height = 1 + max(get_height(root.left), get_height(root.right))
balance = get_balance(root)
if balance > 1:
if get_balance(root.left) < 0:
root.left = left_rotate(root.left)
return right_rotate(root)
if balance < -1:
if get_balance(root.right) > 0:
root.right = right_rotate(root.right)
return left_rotate(root)
return root
最后,实现AVL树的查找操作:
def search(root, key):
if not root or root.key == key:
return root
if key < root.key:
return search(root.left, key)
return search(root.right, key)
时间复杂度分析:
- 插入操作的时间复杂度为O(log n),因为每次插入后,树的高度会减少,从而保证树的平衡性。
- 删除操作的时间复杂度也为O(log n),同样是因为每次删除后,树的高度会减少,从而保证树的平衡性。
- 查找操作的时间复杂度为O(log n),因为在AVL树中,每个节点的左子树和右子树的高度差最多为1,所以查找操作的时间复杂度为O(log n)。