美文网首页
二叉树(下)

二叉树(下)

作者: GallenZhang | 来源:发表于2019-03-15 18:22 被阅读0次

二叉树中有种特殊的树是二叉查找树,其最大的特点就是,支持动态的快速插入、删除、查找操作。

其实除了二叉查找树外,散列表也支持这些操作的,并且比二叉查找树更高效,时间复杂度还是O(1)。既然散列表如此高效,那为什么还会使用二叉查找树呢?

二叉查找树

二叉查找树也叫二叉搜索树,是二叉树最常用的一种类型。二叉查找树为了快速查找而生,除了支持快速查找一个数据,还支持快速插入、删除数据。

二叉查找树的特点:树中的任意一个节点,其左子树中每个节点的值都小于这个节点的值,其右子树中每个节点的值都大于这个节点的值。

1. 查找操作

要在二叉树中查找一个节点 ,先取根节点,如果要查找节点的值等于根节点的值,直接返回。如果要查找节点的值小于根节点的值,就在左子树中递归查找。如果要查找节点的值大于根节点的值,就在右子树中递归查找。

    /**
     * 查找节点
     * @param data
     * @return
     */
    public Node<T> find(T data){
        Node<T> p = root;
        while (p != null){
            if(data.compareTo(p.data) < 0){
                p = p.left;
            }else if(data.compareTo(p.data) > 0){
                p = p.right;
            }else {
                return p;
            }
        }
        return null;
    }

2. 插入操作

往二叉查找树中插入节点,新插入的数据一般都放在叶子节点上。从根节点开始,依次比较要插入数据和节点数据大小关系。

如果要插入数据比节点数据大,并且节点的右子树为空,就将新数据直接插入到右子节点的位置;如果不为空,就继续递归遍历右子树,查找插入位置。如果要插入的数据比节点数据小,并且节点的左子树为空,就将新数据直接插入到左子节点的位置;如果不为空,就继续遍历左子树,找到插入位置。

    /**
     * 二叉搜索树中插入节点
     * @param data
     */
    public void insert(T data){
        if(root == null){
            root = new Node<T>(data);
            return;
        }

        Node<T> p = root;
        while (p != null){
            if(data.compareTo(p.data) < 0){
                if(p.left == null){
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }else {
                if(p.right == null){
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            }
        }
    }

3.删除操作

删除操作相对查找、插入操作复杂一点,针对要删除节点的子节点的个数,我们要分三种情况来处理。

第一种,如果要删除节点没有子节点,只要将要删除节点的父节点,指向删除节点的指针置为null。如下图中的节点55。

第二种,如果要删除节点只有一个子节点(只有左子节点或只有右子节点),只要将要删除节点的父节点原本指向删除节点的指针,重新指向要删除节点的子节点就可以。如下图中的节点13。

第三种,如果要删除节点有两个子节点,这时候情况稍微复杂些。我们需要找到这个节点右子树中最小节点(或者左子树中最大节点),把它替换到要删除的节点上。然后再删除这个最小节点(或者最大节点),因为这个最小节点(或者最大节点)肯定是没有左子节点(或者没有右子节点),接着再应用上面两条规则来删除这个最小节点(或者最大节点)。如下图中的节点18。

    /**
     * 二叉搜索树删除节点
     * @param data
     */
    public void delete(T data){
        Node<T> p = root;
        Node<T> pp = null;

        //查找要删除的节点
        while (p != null && p.data.compareTo(data) != 0){
            pp = p;
            if(data.compareTo(p.data) < 0){
                p = p.left;
            }else {
                p = p.right;
            }
        }

        //没找到要删除的节点
        if(p == null){
            return;
        }

        //要删除节点有左右子节点,将右子树最小节点赋值给要删除节点,然后删除最小节点(p)
        if(p.left != null && p.right != null){
            Node<T> minP = p.right;
            Node<T> minPP = p;
            while (minP.left!= null){
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            p = minP;
            pp = minPP;
        }

        //保存待删除节点的子节点
        Node<T> child = null;
        if(p.left != null){
            child = p.left;
        }else if(p.right != null){
            child = p.right;
        }else {
            child = null;
        }

        //pp为null,表示删除的是根节点,且只有一个子节点
        if(pp == null){
            root = child;
        }else {
            if(pp.right == p){
                pp.right = child;
            }else if(pp.left == p){
                pp.left = child;
            }
        }
    }

4.其他操作

二叉查找树除了插入、删除、查找操作外,还支持快速的查找最大节点和最小节点。

二叉查找树还有一个重要的特性,就是中序遍历查找树,可以有序的输出有序的数据序列,时间复杂度是O(n),非常高效。因为,二叉查找树也叫做二叉排序树。

5.支持重复数据

前面的操作默认二叉查找树是没有重复数据的。但在实际的开发中,我们在二叉树中存储的是一个包含很多个字段的对象,一般会以某个字段作为key来构建二叉树。针对这种有多个key相同的二叉查找树,有两种处理办法。

第一种,二叉查找树中每一个节点不只是存储一个数据,而是通过链表和支持动态扩容的数组等结构,把值相同的数据都存储在同一个节点上,这种办法比较简单。

第二种,每个节点仍然只存储一个数据,这种方式更优雅,但是更复杂了一些。

对于插入操作,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是把这个新插入的数据当做大于这个节点的值来处理。

对于查找操作,遇到值相同的节点,要继续在右子树中查找,直到遇到叶子节点才停止。这样就可以把键值等于要查找值的所有节点找出来。

对于删除操作,我们也需要先查找到每个要删除的节点,然后按照前面删除节点的方法,依次删除。

时间复杂度分析

在最糟糕的情况下,二叉查找树退化成了链表,查找的时间复杂度就变成了O(n)。

在最理想情况下,二叉查找树是一颗完全二叉树,树上任意节点的左右子树都能处于平衡状态。二叉树的高度接近logn,所以插入、删除、查找的时间复杂度是O(logn)。

二叉查找树 VS 散列表

  • 散列表是无序的,若要输出有序数据序列,需要先排序。对于二叉查找树来说,只要中序遍历就可以输出有序序列。
  • 散列表扩容会很耗时,当遇到散列冲突的时候,性能不稳定。尽管二叉查找树的性能不稳定,但是在工程中常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在O(logn)。
  • 散列表的构造比二叉查找树复杂,需要考虑的东西更多。比如散列函数的设计、散列冲突的解决办法、扩容、缩容等。而二叉查找树只要考虑票平衡性这一个问题,这个问题的解决方案比较成熟、固定。
  • 散列表的查找等操作的时间复杂度是常量级的,但是因为哈希冲突的存在,这个常量不一定会比logn小。所以实际上的查找速度不一定会比二叉查找树快。另外哈希函数计算的耗时,也不一定就比平衡二叉查找树的效率高。

综合来看,平衡二叉查找树在某些方面要优于散列表。但是这二者的存在不冲突,在实际开发中,需要结合具体情况来决定到底使用哪一个。

GitHub 代码地址: 二叉查找树

相关文章

  • 面试题32:从上到下打印二叉树

    题目1:不分行从上到下打印二叉树,层次遍历 解析:该问题就是二叉树的层次遍历。 题目2:分行从上到下打印二叉树。 ...

  • 二叉树实现

    今天实现一下二叉树

  • Java数据结构之树

    数据结构之 树 二叉树每个节点最多有两个子树的树结构,在二叉树的概念下又衍生出满二叉树和完全二叉树。满二叉树除最后...

  • 浅谈(二叉树,真,满,完全)

    什么事树形结构? 树的基本概念 下面开始正式进入二叉树。 看一下二叉树的概念。 二叉树的性质如下: 什么是真二叉树...

  • 二叉树的基础+剑指offer32题

    二叉树的简单创建 遍历等题目:不分行从上到下打印二叉树从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺...

  • iOS二叉树算法

    TreeNode是系统类,可以模拟二叉树 tree po一下就能发现是二叉树格式

  • 数据结构与算法 线索二叉树

    线索二叉树原理:在一个二叉树中,在不是完全二叉树的情况下,二叉树结点的左孩子或者右孩子存在为NULL的情况,我们可...

  • 二叉树的基本算法

    一、二叉树的递归遍历 二、二叉树的层次遍历 二叉树的层次遍历是指二叉树从上到下,从左到右遍历数据。同一层中的节点访...

  • Go语言二叉树操作常用技巧

    二叉树经常作为面试题目,一般包含二叉树的遍历和二叉树的查找。自己用GO去写了个小的例子。来加深一下二叉树的操作。 ...

  • 二叉树查找与节点删除的javascript实现

    前言 紧接前面说过的 二叉树的实现 和 二叉树的遍历,今天来说一下用javascript实现二叉树的查找和节点删除...

网友评论

      本文标题:二叉树(下)

      本文链接:https://www.haomeiwen.com/subject/xejapqtx.html