二叉排序树

数据结构中，线性表分为无序线性表和有序线性表。
无序线性表的数据是杂乱无序的，所以在插入和删除时，没有什么必须遵守的规则，可以插入在数据尾部或者删除在数据尾部。但是在查找的时候，需要遍历整个数据表，导致无序线性表的查找效率低。
有序线性表的数据则相反，查找数据时的时候因为数据是有序的，可以用二分法、插值法、斐波那契查找法来实现。但是，当进行插入和删除操作时，需要维护表中数据的有序性，会耗费大量的时间。
那么，我们希望找到一种数据结构，既可以有较高的插入和删除效率，并且具备较高的查找效率，因此，二叉排序树应运而生。

二叉排序树定义

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

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

构造一棵二叉排序树

现有序列：61 87 59 47 35 73 51 98 37 93
构造过程如下：
1）索引 i = 0，A[i] = 61，结点61作为根结点，如图2.1：

图2.1

2）索引 i = 1，A[1] = 87, 87 > 61，且结点61右孩子为空，故81为61结点的右孩子，如图2.2：

图2.2
3）索引 i = 2，A[i] = 59，59 <
61，且结点61左孩子为空，故59为61结点的左孩子，如图2.3：
图2.3
4）索引 i = 3，A[3] = 47，47 < 59，且结点59左孩子为空，故47为59结点的左孩子，如图2.4：
图2.4

5）索引 i = 4，A[4] = 35，35 < 47，且结点47左孩子为空，故35为47结点的左孩子，如图2.5：

图2.5
采用同样规则遍历整个数组得到如图2.6所示的一棵排序二叉树。
图2.6

二叉排序树查找

由二叉树的递归定义性质，二叉排序树的查找同样可以使用如下递归算法查找。

如果树是空的，则查找结束，无匹配。
如果被查找的值和根结点的值相等，查找成功。否则就在子树中继续查找。如果被查找的值小于根结点的值就选择左子树，大于根结点的值就选择右子树。

在理想情况下，每次比较过后，树会被砍掉一半，近乎折半查找。
遍历打印可以使用中序遍历，打印出来的结果是从小到大的有序数组。
查找代码：

    static class Node {

        Object data;
        Node parent;
        Node left;
        Node right;

        public Node(Object data, Node parent, Node left, Node right) {
            this.data = data;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "[data=" + data + "]";
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if (obj.getClass() == Node.class) {
                Node target = (Node) obj;
                return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent;
            }
            return false;
        }

    }

    // 根据给定的值搜索节点
    public Node getNode(T ele) {
        // 从根节点开始搜索
        Node p = root;
        while (p != null) {
            int cmp = ele.compareTo(p.data);
            // 如果搜索的值小于当前p节点的值
            if (cmp < 0) {
                // 向左子树搜索
                p = p.left;
            } else if (cmp > 0) {
                // 如果搜索的值大于当前p节点的值
                // 向右子树搜索
                p = p.right;
            } else {
                return p;
            }
        }
        return null;
    }

对于图2.6所示的二叉排序树，若查找结点key为47则可以查找成功，若查找结点key为75，树中不存在key为75的结点，故查找失败。

二叉排序树插入

二叉排序的插入是建立在二叉排序的查找之上的，插入一个结点，就是通过查找发现该结点合适插入位置，把结点直接放进去。
由此可以得出二叉排序树插入规则如下：

若查找的key已经有在树中，则parent指向该数据结点。
若查找的key没有在树中，则parent指向查找路径上最后一个结点。

例如：若在图2.6展示的二叉排序树中插入结点数据为60的结点。
首先查找结点数据为60的结点，二叉排序树中不存在结点为60的结点，因此查找失败。此时查找指针p指向查找路径最后一个结点即指向59结点。由于60>59且59结点右子树为空，故将60结点作为59结点的右孩子，插入完成。插入后的二叉排序树如图2.8所示。

图2.8

插入代码：

 // 添加节点
    public void add(T ele) {
        // 如果根节点为null
        if (root == null) {
            root = new Node(ele, null, null, null);
        } else {
            Node current = root;
            Node parent = null;
            int cmp = 0;
            // 搜索合适的叶子节点，以该叶子节点为父节点添加新节点
            do {
                parent = current;
                cmp = ele.compareTo(current.data);
                // 如果新节点的值大于当前节点的值
                if (cmp > 0) {
                    // 以右子节点作为当前节点
                    current = current.right;
                } else {
                    // 如果新节点的值小于当前节点的值
                    // 以左节点作为当前节点
                    current = current.left;
                }
            }while (current != null);
            // 创建新节点
            Node newNode = new Node(ele, parent, null, null);
            // 如果新节点的值大于父节点的值
            if (cmp > 0) {
                // 新节点作为父节点的右子节点
                parent.right = newNode;
            } else {
                // 如果新节点的值小于父节点的值
                // 新节点作为父节点的左子节点
                parent.left = newNode;
            }
        }
    }

二叉排序树删除

二叉树的删除可不再像二叉树的插入那么容易了，以为删除某个结点以后，会影响到树的其它部分的结构。
删除的时候需要考虑以下几种情况：

1）删除结点为叶子结点；
2）删除的结点只有左子树；
3）删除的结点只有右子树
4）删除的结点既有左子树又有右子树。

考虑前三种情况，处理方式比较简单。
例如：若要删除图2.8中的结点93，则直接删除该结点即可。删除后二叉排序树如图2.9所示：

图2.9

若要删除的结点为结点35，结点35只有右子树，只需删除结点35，将右子树37结点替代结点35即可。删除后的二叉排序树如图2.10所示：

图2.10

删除只有左子树的结点与此情况类似。
情况4相对比较复杂，对于待删除结点既有左子树又有右子树的情形，最佳办法是在剩余的序列中找到最为接近的结点来代替删除结点。这种代替并不会影响到树的整体结构。那么最为接近的结点如何获取呢？
可以采用中序遍历的方式来得到删除结点的前驱和后继结点。选取前驱结点或者后继结点代替删除结点即可。
例如：待删除的结点为47，图2.8中二叉排序树的中序遍历序列为35 37 47 51 59 60 61 73 87 93 98。则结点47的前驱结点为37，则直接将37结点替代47结点即可。替换后的二叉排序树如图2.11所示：

图2.11

删除代码：

    // 删除节点
    public void remove(T ele) {
        // 获取要删除的节点
        Node target = getNode(ele);
        if (target == null) {
            return;
        }
        // 左、右子树为空
        if (target.left == null && target.right == null) {
            // 被删除节点是根节点
            if (target == root) {
                root = null;
            } else {
                // 被删除节点是父节点的左子节点
                if (target == target.parent.left) {
                    // 将target的父节点的left设为null
                    target.parent.left = null;
                } else {
                    // 将target的父节点的right设为null
                    target.parent.right = null;
                }
                target.parent = null;
            }
        } else if (target.left == null && target.right != null) {
            // 左子树为空，右子树不为空
            // 被删除节点是根节点
            if (target == root) {
                root = target.right;
            } else {
                // 被删除节点是父节点的左子节点
                if (target == target.parent.left) {
                    // 让target的父节点的left指向target的右子树
                    target.parent.left = target.right;
                } else {
                    // 让target的父节点的right指向target的右子树
                    target.parent.right = target.right;
                }
                // 让target的右子树的parent指向target的parent
                target.right.parent = target.parent;
            }
        } else if (target.left != null && target.right == null) {
            // 左子树不为空，右子树为空
            // 被删除节点是根节点
            if (target == root) {
                root = target.left;
            } else {
                // 被删除节点是父节点的左子节点
                if (target == target.parent.left) {
                    // 让target的父节点的left指向target的左子树
                    target.parent.left = target.left;
                } else {
                    // 让target的父节点的right指向target的左子树
                    target.parent.right = target.left;
                }
                // 让target的左子树的parent指向target的parent
                target.left.parent = target.parent;
            }
        } else {
            // 左、右子树都不为空
            // leftMaxNode用于保存target节点的左子树中值最大的节点
            Node leftMaxNode = target.left;
            // 搜索target节点的左子树中值最大的节点
            while (leftMaxNode.right != null) {
                leftMaxNode = leftMaxNode.right;
            }
            // 从原来的子树中删除leftMaxNode节点
            leftMaxNode.parent.right = null;
            // 让leftMaxNode的parent指向target的parent
            leftMaxNode.parent = target.parent;
            // 被删除节点是父节点的左子节点
            if (target == target.parent.left) {
                // 让target的父节点的left指向leftMaxNode
                target.parent.left = leftMaxNode;
            } else {
                // 让target的父节点的right指向leftMaxNode
                target.parent.right = leftMaxNode;
            }
            leftMaxNode.left = target.left;
            leftMaxNode.right = target.right;
            target.parent = target.left = target.right = null;
        }
    }

总结

二叉排序树是一种查找与插入效率均较为高效的数据结构，同时，二叉排序树也是二叉树学习中的重点与难点。希望通过本篇的学习能够掌握二叉排序树的查找、插入与删除等基本操作。