BST二叉搜索树

概述

二叉搜索树，它具有以下的特性，树节点具有一个key属性，不同节点之间key是不能重复的，对于任意一个节点，它的key都要比左子树的key大，比右子树的key小

实现

创建节点

static class BSTNode {
        int key;
        Object value;
        BSTNode left;
        BSTNode right;

        public BSTNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }

        public BSTNode(int key, Object value, BSTNode left, BSTNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

查找节点

利用二叉树的性质

public Object get(int key) {
        BSTNode node = root;
        while (node != null) {
            if (node.key < key) {
                node = node.right;
            } else if (node.key > key) {
                node = node.left;
            } else {
                return node.value;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

增加节点

同样利用二叉树的性质，但是需要记录要增加的节点的父节点

public void put(int key, Object value) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            parent = node;
            if (key < node.key) {
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
            //直接修改
                node.value = value;
                return;
            }
        }
        if (parent == null) {
            root = new BSTNode(key, value);
        } else if (key > parent.key) {
            parent.right = new BSTNode(key, value);
        } else {
            parent.left = new BSTNode(key, value);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

查找后驱值

在后面的AVL，以及红黑树中删除节点是，我们经常会需要求一个节点的后驱节点

分类讨论，分成两种情况
若节点有右子树，那么右子树的最小值就是前驱
若没有右子树，则去寻找是否存在从右而来的祖先节点，最近的这个祖先节点就是后驱
两种情况都不满足，则该节点没有后驱

public Object predecessor(int key) {
        BSTNode ancestorFromRight = null;
        BSTNode node = root;
        while (node != null) {
            if (key < node.key) {
                ancestorFromRight = node;
                node = node.left;
            } else if (key > node.key) {
                node = node.right;
            } else {
                break;
            }
        }

        //没有该节点
        if (node == null) {
            return null;
        }
        if (node.right != null) {
            return min(node.right);
        }
        return ancestorFromRight == null ? null : ancestorFromRight.value;
    }
    
   
public Object min(BSTNode node) {
        if (node == null) {
            return null;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node.value;
    }
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

根据关键词删除

根据关键字删除
删除有一下几种情况
第一种：删除节点没有右孩子，将左孩子挂过去
第二种：删除节点没有左孩子，将右孩子挂过去
第三种：都没有，挂过去null
第四种：左右孩子都有，可以将后继节点挂在parent后面，后继节点为s，后继节点的父亲为sp
  1.将如果sp就是要删除的节点
  2.sp不是删除节点，需要将s的后代给sp

public Object delete(int key) {
        BSTNode node = root;
        BSTNode parent = null;
        while (node != null) {
            if (key < node.key) {
                parent = node;
                node = node.left;
            } else if (key > node.key) {
                parent = node;
                node = node.right;
            } else {
                break;
            }
        }
        if (node == null) {
            return null;
        }

        if (node.left == null) {
            //情况1
            shift(parent, node, node.right);
            //情况2
        } else if (node.right == null) {
            shift(parent, node, node.left);
        } else {

            BSTNode s = node.right;
            BSTNode sParent = node;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }

            if (sParent != node) {
                //将后驱节点的孩子挂在后驱节点父亲的后面
                shift(sParent, s, s.right);
                s.right = node.right;
            }

            //后驱节点一定没有左孩子，所以可以直接的挂靠
            shift(parent, node, s);
            s.left = node.left;

        }
        return node.value;
    }


    /*
     * 托孤方法
     *
     * */
    private void shift(BSTNode parent, BSTNode deleted, BSTNode child) {
        if (parent == null) {
            root = child;
        } else if (deleted == parent.left) {
            parent.left = child;
        } else {
            parent.right = child;
        }
    }
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

找到树中所有小于key的节点的value

我们可以通过一个中序遍历实现，对于一个二叉搜索树来说，中序遍历的结果，恰好是从小到大排序的

public List<Object> less(int key) {
        ArrayList<Object> result = new ArrayList<>();
        LinkedList<BSTNode> stack = new LinkedList<>();
        BSTNode node = root;
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                BSTNode min = stack.pop();
                if (min.key < key) {
                    result.add(min.value);
                } else {
                    break;
                }
                node = min.right;
            }
        }
        return result;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20