重温数据结构_树的查找

线性表的查找的顺序查找和折半查找作为查找表的组织形式，其中折半查找效率较高。但由于折半查找要求表中记录按关键字有序排列，且不能用链表做存储结构，因此当表的插入或删除操作频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引用的额外时间开销，就会抵消折半查找的优点。所以，线性表的查找更适用于静态查找表，若要对动态查找表进行高效率的查找，可采用几种特殊的二叉树作为查找表的组织形式，在此将它们统称为树表。

二叉排序树定义

二叉排序树又称二叉查找树或二叉搜索树，这是一种插入、删除和查找记录效率都很高的树结构。

二叉排序树是具有下列性质的二叉树(BST性质)：

若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
若它的右子树不空，则右子树上所有节点的值均大于根结点的值；
它的左、右子树也分别为二叉排序树。

二叉排序树性质

二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一个二叉树时可以得到一个结点值递增的有序序列。

二叉树的遍历

二叉树的遍历有三种方式，如下：

前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树。简记根-左-右。
中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树。简记左-根-右。
后序遍历（LRD），首先遍历左子树，然后遍历右子树，最后访问根结点。简记左-右-根。

二叉排序树的算法

二叉排序树的查找

因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行查找和折半查找类似，也是一个逐步缩小查找范围的过程。
** 采用循环遍历方式查找：**

    /**
     * 根据给定值，从最顶层树根节点循环遍历地开始查找某结点
     * 
     * @param node
     *            最顶层树根节点
     * @param data
     *            需要进行查找的值
     * @return 如果找到则返回对应TreeNode对象，否则返回null
     */
    public TreeNode findTreeNodeBy循环(TreeNode node, Integer data) {
        while (node != null) {
            if (node.data > data) {
                node = node.left;
            } else if (node.data < data) {
                node = node.right;
            } else {
                return node;
            }

        }
        return null;
    }

采用递归方式查找：

    /**
     * 根据给定值，从最顶层树根节点递归地开始查找某结点
     * 
     * @param node
     *            最顶层树根节点
     * @param data
     *            需要进行查找的值
     * @return 如果找到则返回对应TreeNode对象，否则返回null
     */
    public TreeNode findTreeNodeBy递归(TreeNode node, Integer data) {

        if ((node == null) || node.data == data) {
            return node;
        } else if (node.data > data) {
            return findTreeNodeBy递归(node.left, data);
        } else {
            return findTreeNodeBy递归(node.right, data);
        }

    }

可见，二叉排序树上的查找和折半查找相差不大。但就维护表的有序性而言，二叉排序树更加有效，因为无需移动记录，只需修改指针即可完成对结点的插入和删除操作。因此，对于需要经常进行插入、删除和查找运算的表，采用二叉排序树比较好。

二叉排序树插入

二叉排序树的插入操作是以查找为基础的。要将一个关键字值为key的结点插入到二叉排序树中，则需要从根节点向下查找，当树中不存在关键字等于key的结点时才进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

** 采用循环遍历方式查找：**

    /**
     * 循环方式向二叉排序树插入数据
     * 
     * @param key
     */
    public void insertBSTBy循环(int key) {
        TreeNode node = root;
        /** 记录查找结点的前一个结点 */
        TreeNode parent = null;
        /** 一直查找下去，直到到达满足条件的结点位置 */
        while (node != null) {
            parent = node;
            if (key < node.data)
                node = node.left;
            else if (key > node.data)
                node = node.right;
            else
                return;
        }
        
        TreeNode treeNode = new TreeNode(key);
        if (root == null)
            root = treeNode;
        else if (key < parent.data) {
            parent.left = treeNode;
        } else{
            parent.right = treeNode;
        }
    }

采用递归方式查找：

    /**
     * 往树中加节点
     * 
     * @param data
     * @return Boolean 插入成功返回true
     */
    public Boolean insertBSTBy递归(Integer data) {

        // 生成最顶层根节点
        if (null == root) {
            root = new TreeNode(data);
            System.out.println("数据成功插入到二叉查找树中");
            return true;
        }

        return insertBSTBy递归(root, data);

    }

    /**
     * 递归方式向二叉排序树插入数据
     * 
     * @param node
     * @param data
     * @return
     */
    private boolean insertBSTBy递归(TreeNode node, Integer data) {
        if (data < node.data) {
            if (node.left == null) {
                TreeNode treeNode = new TreeNode(data);
                node.left = treeNode;
                return true;
            } else {
                insertBSTBy递归(node.left, data);
            }
        } else if (data > node.data) {
            if (node.right == null) {
                TreeNode treeNode = new TreeNode(data);
                node.right = treeNode;
                return true;
            } else {
                insertBSTBy递归(node.right, data);
            }
        }

        return false;
    }

算法分析：
二叉排序树插入的基本过程是查找，所以时间复杂度同查找一样，是O(㏒2n)。

二叉排序树的删除

删除二叉排序树中的结点分为三种情况：
（1）要删除的结点是叶子结点，只需要修改左右结点的指针为空；
（2）若只有左子树或者只有右子树，直接让左子树/右子树代替
（3）若既有左子树，又有右子树，用左子树中最大的那个值（即最右端）代替要删除的结点并将其删除，重接其左子树

代码实现待补充

平衡二叉树(AVL树)

定义

二叉排序树查找算法的性能取决于二叉树的结构，而二叉排序树的形状则取决于其数据集。如果数据呈有序排列，则二叉排序树是线性的，查找的时间复杂度为O(n)；反之，如果二叉排序树的结构合理，则查找速度较快，查找的时间复杂度为O(log2n)(以2为底n的对数)。事实上，树的高度越小，查找速度越快。因此，希望二叉树的高度尽可能小。

平衡二叉树是对二叉查找树的一种改进。

平衡二叉树或是空树，或者是具有如下特征的二叉排序树。

左子树和右子树的深度之差的绝对值不超过1。
左子树和右子树也是平衡二叉树。
若将二叉树上结点的平衡因子定义为该结点左子树和右子树的深度之差，则平衡二叉树上所有结点的平衡因子只可能是-1，0和1.只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

图片来源百度图片

调整方法

基本思路：当往二叉查找树种插入一个结点时，首先检查是否因为插入而破坏了平衡。若破坏了则找出其中的最小不平衡二叉树，在保持二叉查找树特性的情况下，调整最小不平衡子树中结点之间的关系，以达到平衡。

最小不平衡二叉树：指距离插入结点最近且以平衡因子的绝对值大于1的结点作为跟的子树。

最小不平衡二叉树结点的关系到底是如何进行调整的呢？有这四种情况导致二叉排序树不平衡：

以AVL树为例理解二叉树的旋转（Rotate）操作

代码实现

待补充