数据结构之二叉搜索树

二叉搜索树

二叉搜索树也叫二叉查找树或者二叉排序树，它要么是一颗空树，要么满足以下几点：
1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
3. 任意节点的左、右子树也分别为二叉搜索树。
4. 没有键值相等的节点。

二叉搜索树的实现

1. 二叉搜索树的存储结构

public class BinarySearchTree {
    public static  Node root;
    public BinarySearchTree(){this.root = null;}
}
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
        left = null;
        right = null;
    }
}

2. 二叉搜索树的插入
a. 循环二分查找到需要插入的地方。
b. 假如插入的值小于当前的值，并且当前左节点为空，那么左节点就指向新节点。
c. 假如插入的值大于当前的值，并且当前右节点为空，那么右节点就指向新节点。

public void insert(int id){Node newNode = new Node(id);
    if(root == null){
        root = newNode;
        return;
    }
    Node current = root;
    Node parent = null;
    while(true){
        parent = current;
        if(id < current.data){
            current = current.left;
            if(current == null){
                parent.left = newNode;
                return;
            }
        } else {
            current = current.right;
            if(current == null){
                parent.right = newNode;
                return;
            }
        }
    }
}

3. 二叉搜索树的删除
a. 当删除节点为叶子节点时，直接删除节点。
b. 当删除节点只有左子树时，重接左子树。
c. 当删除节点只有右子树时，重接右子树。
d. 当删除节点既有左子树，又有右子树时，先找一个可以替换删除节点的节点。由于二叉树的性质，左子树的值小于根节点的值，右子树的值大于根节点的值。所以右子树的最左的节点就是替换删除的节点，然后在重接右子树。
第 d 点的图例：

public boolean delete(int id) {
    Node parent = root;
    Node current = root;
    boolean isLeftChild = false;
    while (current.data != id) {
        parent = current;
        if (current.data > id) {
            isLeftChild = true;
            current = current.left;
        } else {
            isLeftChild = false;
            current = current.right;
        }
        if (current == null) {return false;}
    }
    // 删除的节点既没左节点，也没右节点
    if (current.left == null && current.right == null) {if (current == root) {root = null;}
        if (isLeftChild == true) {parent.left = null;} else {parent.right = null;}
    }
    // 删除的节点只有左节点
    else if (current.right == null) {if (current == root) {root = current.left;} else if (isLeftChild) {parent.left = current.left;} else {parent.right = current.left;}

    }
    // 删除的节点只有右节点
    else if (current.left == null) {if (current == root) {root = current.right;} else if (isLeftChild) {parent.left = current.right;} else {parent.right = current.right;}
    }
    // 删除的节点既有左节点，又有右节点
    else if (current.left != null && current.right != null) {
        // 找到右子树的最左节点
        Node successor = getSuccessor(current);
        if (current == root) {root = successor;} else if (isLeftChild) {parent.left = successor;} else {parent.right = successor;}
            successor.left = current.left;
        }
        return true;
    }

    public Node getSuccessor(Node deleleNode) {
        Node successsor = null;
        Node successsorParent = null;
        Node current = deleleNode.right;
        while (current != null) {
            successsorParent = successsor;
            successsor = current;
            current = current.left;
        }
        if (successsor != deleleNode.right) {
            successsorParent.left = successsor.right;
            successsor.right = deleleNode.right;
        }
        return successsor;
    }

4. 二叉搜索树的查找

public boolean find(int id) {
    Node current = root;
    while (current != null) {if (current.data == id) {return true;} else if (current.data > id) {current = current.left;} else {current = current.right;}
    }
    return false;
    }

总结

由于它是一颗有序的树，就可以进行折半查找，每一次查找，假如不是匹配的值，都可以排除一半的值。所以一般的时间复杂度是 O(log n)。假如这棵树退化为斜树，就差不多是线性表了，它的时间复杂度就是 O(n)。

虽然二叉搜索树的最坏时间复杂度是 O(n)，但通过一些改进可以把最坏时间复杂度降至 O(log n)，比如 AVL 树、红黑树等。红黑树不需要绝对的平衡，所以插入和删除效率上要高，在 JDK1.8 中哈希表存储大于等于 8 个节点的链表就是采用的红黑树。

所以二叉搜索树在查找上是非常快的，在一些需要很高查询效率上推荐使用。

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊 」。
欢迎一起谈天说地，聊代码。