搜索树与哈希表详解_二叉搜索树比哈希表在什么操作下速度更快

---

一、搜索树

1.1 概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值；
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值；
• 它的左右子树也分别为二叉搜索树。

如：

1.2 查找

若根节点不为空:
如果根节点==查找key 返回当前节点；
如果根节点 >查找key在其左子树查找；
如果根节点<查找key在其右子树查找；否则就是没有找到，返回null；

class Node{
   
    public int val;
    public  Node left;
    public Node right;
    public Node(int val){
   
        this.val = val;
    }
}
//二叉搜索树
public class BinarySearchTree {
   
    public Node root = null;
    //查找
    public Node  search(int key){
   
        Node cur = root;
        while (cur != null){
   
            if(cur.val == key){
   
                return cur;
            }else if(cur.val < key){
   
                cur = cur.right;
            }else{
   
                cur = cur.left;
            }
        }
        return null;
    }

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

1.3 插入

1. 用cur和parent来找到val需要存储的位置。
2. parent.val 和val比较大小，确定是在左边还是在右边进行插入。

public boolean insert(int val) {
   
        if(root == null) {
   
            root = new Node(val);
            return true;
        }

        Node cur = root;
        Node parent = null;
        while (cur != null) {
   
            if(cur.val < val) {
   
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val) {
   
                return false;//不能有相同的数据
            }else {
   
                parent = cur;
                cur = cur.left;
            }
        }
        Node node = new Node(val);
        if(parent.val < val) {
   
            parent.right = node;
        }else {
   
            parent.left = node;
        }
        return true;
    }
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

1.4 删除

设待删除结点为 cur, 待删除结点的双亲结点为 parent；

1. cur.left == null

• cur 是 root，则 root = cur.right
  

• cur 不是 root，cur 是 parent.left，则 parent.left = cur.right

• cur 不是 root，cur 是 parent.right，则 parent.right = cur.right
  

• cur.right == null

• cur 是 root，则 root = cur.left
  

• cur 不是 root，cur 是 parent.left，则 parent.left = cur.left
  

• cur 不是 root，cur 是 parent.right，则 parent.right = cur.left
  

• cur.left != null && cur.right != null
  需要使用替换法进行删除：

• 在cur的左树当中找最大值或者在cur的右树中找最小值
  用它的值填补到被删除节点中，再来处理该结点的删除问题。

/**
 * Created With IntelliJ IDEA
 * Description:
 * Users: yyyyy
 * Date: 2022-02-19
 * Time: 16:43
 *
 */
class Node{
   
    public int val;
    public  Node left;
    public Node right;
    public Node(int val){
   
        this.val = val;
    }
}
//二叉搜索树
public class BinarySearchTree {
   
    public Node root = null;
    //查找
    public Node  search(int key){
   
        Node cur = root;
        while (cur != null){
   
            if(cur.val == key){
   
                return cur;
            }else if(cur.val < key){
   
                cur = cur.right;
            }else{
   
                cur = cur.left;
            }
        }
        return null;
    }

    //插入
    public boolean insert(int val) {
   
        if(root == null) {
   
            root = new Node(val);
            return true;
        }

        Node cur = root;
        Node parent = null;
        while (cur != null) {
   
            if(cur.val < val) {
   
                parent = cur;
                cur = cur.right;
            }else if(cur.val == val) 
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59