算法学习9——二叉搜索树
时间: 2023-10-27 22:07:23 浏览: 49
二叉搜索树,也叫二叉查找树(BST,Binary Search Tree),是一种特殊的二叉树。相对于普通的二叉树,它有一个特点:所有左子树的节点都比根节点小,所有右子树的节点都比根节点大。因此,它可以快速地进行查找、插入、删除等操作。
具体来说,二叉搜索树的定义如下:
- 节点的左子树中所有节点的值都小于该节点的值。
- 节点的右子树中所有节点的值都大于该节点的值。
- 左右子树也都是二叉搜索树。
如下图所示,就是一个二叉搜索树的例子:
```
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
```
在这个树中,每个节点都满足左子树的节点值小于该节点的值,右子树的节点值大于该节点的值。比如,节点 3 的左子树是 1 和 6,右子树是 4 和 7,都满足要求。
二叉搜索树的主要操作包括查找、插入和删除。
查找操作可以通过递归或者循环实现。递归实现如下:
```
def search(root, val):
if not root or root.val == val:
return root
if root.val > val:
return search(root.left, val)
else:
return search(root.right, val)
```
插入操作需要先查找到插入的位置,然后创建一个新节点插入到该位置:
```
def insert(root, val):
if not root:
return TreeNode(val)
if root.val > val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
```
删除操作比较复杂,需要考虑多种情况。如果要删除的节点只有一个子节点,直接将其子节点替换上来即可。如果要删除的节点有两个子节点,可以找到其右子树中的最小节点(或者左子树中的最大节点)来替换该节点,然后再删除该最小节点(或者最大节点)。
```
def delete(root, val):
if not root:
return None
if root.val == val:
if not root.left:
return root.right
elif not root.right:
return root.left
else:
# 找到右子树中的最小节点
p = root.right
while p.left:
p = p.left
root.val = p.val
root.right = delete(root.right, p.val)
elif root.val > val:
root.left = delete(root.left, val)
else:
root.right = delete(root.right, val)
return root
```
需要注意的是,在删除节点时,要保证删除后的树仍然是二叉搜索树。