抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

简称 BST,也称二叉排序树或二叉查找树。

特点:

  • 任一结点 > 其左子树的所有结点,
    并且< 其右子树的所有结点;
  • 结点的左、右子树,也是二叉排序树;
  • 每个结点键值唯一(不能重复)

重要性质:

  • 中序遍历二叉排序树得到递增序列

所以判断 1 棵二叉树是否是二叉排序树?
只要中序遍历,得到递增序列才是。

插入

  • 若当前树为空,则新结点为根
  • 若当前树不空,
    将待插入 x 与根比较;
    • 若 x 等于根,不用插入
    • 若 x 大于根,则去右子树 (找位置);
    • 若 x 小于根,则去左子树 (找位置);

可以总结为:

插入之前,先查找:

  • 若找到,不用插入
  • 若找不到,则在到达的空位置处,放入 x;

所以最新插入的结点,一定是叶子;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func insertIntoBST(root *TreeNode, val int) *TreeNode {
if root == nil {
return &TreeNode{
Val: val,
}
}
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
}
if root.Val < val {
root.Right = insertIntoBST(root.Right, val)
}
return root
}

查找

  • 从根结点开始,如果树为空,则返回 NULL
  • 如果非空,从根结点开始,比较待检索的键值
    • 若相等,则成功;

    • 若小于根,
      则去根的左子树;

    • 若大于根,
      则去根的右子树,

迭代
1
2
3
4
5
6
7
8
9
10
11
12
func searchBST(root *TreeNode, val int) *TreeNode {
for root != nil {
if root.Val > val {
root = root.Left
} else if root.Val < val {
root = root.Right
} else {
return root
}
}
return nil
}

删除

考虑三种情况:

  • ① 要删除叶子结点
    直接删除,并将父结点指针置为 NULL
  • ② 删除只有 1 个孩子的结点
    将父结点指针指向要删除结点的孩子结点
  • ③ 删除有左右子树的结点
    用另一个结点替代删除的结点:
    • 右子树的最小元素 或者 左子树的最大元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return root
}
if root.Val > key {
root.Left = deleteNode(root.Left, key)
return root
}
if root.Val < key {
root.Right = deleteNode(root.Right, key)
return root
}
// 情况 1 : 以下两个 if 已经处理
if root.Left == nil { // 情况 2 左
return root.Right
}
if root.Right == nil { // 情况 2 右
return root.Left
}
// 情况 3 : 使用右子树最小元素
minNode := root.Right
for minNode.Left != nil {
minNode = minNode.Left
}
root.Val = minNode.Val
root.Right = deleteNode(root.Right, minNode.Val)
return root
}

平均检索长度 ASL

比较次数:不大于树的深度

最坏平均查找长度 ASL:(n+1)/2

最好 ASL:$log2(n)$ (参考二分查找)

所有操作的复杂度都是 $O(logn)$

评论



本站总访问量为 访客数为