二叉搜索树

Posted on | Edited on | In ,

二叉查找树的定义（Binary Search Tree）

左子树每个节点的值要小于节点值，右子树每个节点的值都要大于该节点的值。对于大小相等的节点，两种做法，链表或者数组的方式保存，一种是当做大于该节点放在右子树，本文取第二种方法

二叉查找树的查找操作

遍历或者递归查找树，如果该值小于节点的值从左子树查找，如果大于大于根节点从有子树查找

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
//遍历方法
public static List<TreeNode> find(TreeNode tree, int value) {
    TreeNode p = tree;
    List<TreeNode> treeNodes = new ArrayList<>();
    while (p != null) {
        if (value >= p.value) {
            if (p.value == value) {
                treeNodes.add(p);
            }
            p = p.right;
        } else {
            p = p.left;
        }
    }

    return treeNodes;
}

//递归
public static List<TreeNode> find(TreeNode tree, int value) {
    TreeNode p = tree;
    List<TreeNode> treeNodes = new ArrayList<>();
    if (value < p.value && p.left != null) {
        findNodeByValue(p.left, value, treeNodes);
    }

    if (value >= p.value && p.right != null) {
       findNodeByValue(p.right, value, treeNodes);
    }
    return treeNodes;
}

private static void findNodeByValue(TreeNode tree, int value, List<TreeNode> treeNodes) {
    if (tree == null) {
        return;
    }

    if (value < tree.value) {
        findNodeByValue(tree.left, value, treeNodes);
    }else{
        // if (value >= tree.value)
        if (value == tree.value) {
            treeNodes.add(tree);
        }
        findNodeByValue(tree.right, value, treeNodes);
    }
}

二叉查找树的添加操作

新插入的值一般在叶子节点，所以遍历树，如果小于节点值，并且做节点是空就插入到左子树，如果大于节点的值并且节点为空插入有子树，否则继续遍历

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
//遍历
public static void insertNode(TreeNode treeNode, int v) {

    TreeNode p = treeNode;
    while (p != null) {
        if (v<p.value) {
            if (p.left == null) {
                p.left = new TreeNode(v);
                return;
            }

            p = p.left;
        } else {
            //
            if (p.right == null) {
                p.right = new TreeNode(v);
                return;
            }

            p = p.right;
        }
    }
}

//递归
public static void insertNode(TreeNode treeNode, int v) {
    TreeNode p = treeNode;
    if (v < p.value) {
        if (p.left == null) {
            p.left = new TreeNode(v);
            return;
        }
        insertNode(p.left, v);
    } else if (v >= p.value) {
        if (p.right == null) {
            p.right = new TreeNode(v);
            return;
        }
        insertNode(p.right, v);
    }
}

二叉查找树的删除

  1. 找到该节点， 如果遇到冲突，放在数组中
  2. 如果查找的节点叶子节点直接将父节点指向null
    1. 如果只有左（右）子树，将该节点指向改节点中的左（右）子树
    2. 如果既有左子树，又有右子树，找第一个大于该节点的节点a，将a的值复制到该节点，然后删除a。
  3. 从数组逆向遍历一个个删除。
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
60
61
62
63
64
65
66
67
68
69
public static TreeNode delNode(TreeNode tree, int v) {
    //遍历树，找到相等节点放在eqNodes父节点放在pNodes
    TreeNode node = tree;
    List<TreeNode> eqNodes = new ArrayList<>();
    List<TreeNode> pNodes = new ArrayList<>();
    while (node != null) {
        if (v < node.value) {
            if (node.left!=null && node.left.value == v) {
                eqNodes.add(node.left);
                pNodes.add(node);
            }

            node = node.left;
        } else {
            if (node.right!=null && node.right.value == v) {
                eqNodes.add(node.right);
                pNodes.add(node);
            }
            node = node.right;
        }
    }

    //没有相等的
    if (eqNodes.size() == 0) {
        return tree;
    }

    //后续遍历相等的节点一次删除
    for (int i = eqNodes.size() - 1; i >= 0; i--) {
        node = eqNodes.get(i);
        TreeNode parent = pNodes.get(i);

        //同时有左右子树，找到右子树里最小的节点和父节点，将右子树最小的节点的值复制给之前要删除的节点
        while (node.left != null && node.right != null) {
            TreeNode minNode = node.right;
            TreeNode minPNode = node;
            while (minNode.left != null) {
                minPNode = minNode;
                minNode = minPNode.left;
            }

            //复制
            node.value = minNode.value;
            //删除右子树最小的节点
            node = minNode;
            parent = minPNode;
        }

        //找到child树，不会出现左右子树同时存在的情况：P
        TreeNode child = null;
        if (node.left != null) {
            child = node.left;
        } else if (node.right != null) {
            child = node.right;
        }

        //开始删除如果parent是空，删的是根节点，如果node<parent删除的是左子树，反之是右子树
        if (parent == null) {
            tree = child;
        } else if (node.value < parent.value) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }

    return tree;

}

时间复杂度

查找、删除、添加的逻辑都是类似的时间复杂度和树的高度相关。节点和高度的关系如下:
以完全二叉树为例，假设树的层级是H，非叶子节点是：1+2+4+8+…+(2的H-1次方)，叶子节点是【1~2的H次方】。H就是log(n-1)+1~Logn之间，所以时间复杂度是logN

最坏情况

破坏平衡退化成链表。

搜索树和散列比的其他功能

搜索数能很方便的找到最小节点、最大节点、找到前驱节点和后置节点代码如下。

搜索数如果想按从小到大打印可以通过中序遍历2Logn比散列要快。

和散列对比其他的优势：

  1. 散列虽然查找是o(1)，但是考虑到hash函数以及hash冲突要遍历链表以及开发寻址，所以不一定效率高
  2. hash冲突导致性能不稳定，搜索树通过平衡性能很稳定
  3. 散列需要扩容和缩容额外需要资源
  4. 负载因子不能太大容易造成内存浪费