数据结构：二叉搜索树

发表于

基本概念

二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树），它或者是一棵空树，或者是具有下列性质的二叉树：

  • 若左子树不空，则左子树上所有结点的值均小于它的根结构的值
  • 若右子树不空，则右子树上所有结点的值均大于它的根结点的值
  • 它的左右子树也分别是二叉查找树

规律:
一棵BST节点数为l，索引从0开始。对于索引为i的节点，

  • 二叉排序树进行中序遍历可得到一个有序序列
  • 其左子树节点索引为2i+1,右子树节点索引为2i+2,
  • 父节点索引为(i-1)/2
  • 最后一个非叶子节点索引为l/2-1

解释说明: 构造二叉排序树不是为了排序，而是为了提高查找和插入的速度。在一个有序数据集上的查找速度总是要快于无序的数据集的，而且二叉排序树这种链式存储结构，也有利于插入和删除的速度。

操作

新建

1
2
3
4
5
6
7
8
9
10
11
12
func generate(arr []int)*TreeNode{
    var root *TreeNode
    for _,v:=range arr{
        if root==nil{
            root = &TreeNode{Val:v}
        }else{
            insert(root,&TreeNode{Val:v})
        }
    }
    return root
}

查找

1
2
3
4
5
6
7
8
9
10
11
12
13
func search(root *TreeNode,key int)*TreeNode{
    if root==nil{
        return root
    }
    if root.Val==key{
        return root
    }else if key<root.Val{
        return search(root.Left,key)
    }else{
        return search(root.Right,key)
    }
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func insert(root *TreeNode,node *TreeNode){
    if root.Val==node.Val{
        return
    }
    if node.Val<root.Val{
        if root.Left==nil{
            root.Left=node
        }else{
            insert(root.Left,node)
        }
    }else{
        if root.Right==nil{
            root.Right=node
        }else{
            insert(root.Right,node)
        }
    }
}

删除

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 delete(root *TreeNode,key int)*TreeNode{
    if root==nil{
        return root
    }
    if root.Val==key{
        if root.Left==nil && root.Right ==nil{
            return nil
        }else if root.Left==nil{
            return root.Right
        }else if root.Right ==nil{
            return root.Left
        }else{
            successor:=findMinNode(root.Right)
            successor_copy:=&TreeNode{Val:successor.Val}
            successor_copy.Left = root.Left
            successor_copy.Right = removeMinNode(root.Right)
            return successor_copy
        }
    }else if root.Val>key{
        root.Left = delete(root.Left,key)
        return root
    }else{
        root.Right = delete(root.Right,key)
        return root
    }
}

常用逻辑块

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
29
30
31
32
33
34
35
//查找并返回BST最小的节点
func findMinNode(root *TreeNode)*TreeNode{
    if root==nil{
        return nil
    }
    for root.Left!=nil{
        root = root.Left
    }
    return root
}
//删除BST最小节点，并返回新根节点
func removeMinNode(root *TreeNode)*TreeNode{
    if root==nil{
        return nil
    }
    //root.Left==nil时，root是最小的节点，删除root后返回root.Right
    if root.Left==nil{
        tmp:=root.Right
        root.Right = nil    //为什么要执行这个动作？
        return tmp
    }
    //当root.Left!=nil时，对root左子树继续查找删除
    root.Left = removeMinNode(root.Left)
    return root
}
问题:如果不把待删除节点的左右节点设置为nil会怎么样？
如果不把待删除节点的左右节点设置为 nil ，也即是把 root.left = nil root.right = nil 这两行代码注释掉，也可以得到一个 Accept。
写这两行代码是出于面向对象的程序语言（Python 和 Java 都是）的垃圾回收机制（Garbage Collection，GC）的考虑。如果一个对象没有被其它对象引用，它会在合适的时候被垃圾回收机制回收，被垃圾回收机制回收即是真正从内存中删除了，语义上也没有必要保留这两个引用。
“垃圾回收机制”不在我能讲解的范围内，建议搜索该关键字获得相关的知识。欢迎讨论。