设为首页 - 加入收藏 华夏网 ()- 云主机,资讯,互联网,人工智能,云计算,大赢家论坛,区块链,VR,站长网!
热搜: 平台 google 2019 中国
当前位置: 主页 > 电商 > 正文

自己动手实现java数据结构(六)二叉搜索树

发布时间:2021-04-04 12:16 所属栏目:[电商] 来源:网络整理
导读:1.二叉搜索树介绍 前面我们已经介绍过了向量和链表。有序向量可以以二分查找的方式高效的查找特定元素,而缺点是插入删除的效率较低(需要整体移动内部元素);链表的优点在于插入,删除元素时效率较高,但由于不支持随机访问,特定元素的查找效率为线性复杂度

1.二叉搜索树介绍

  前面我们已经介绍过了向量和链表。有序向量可以以二分查找的方式高效的查找特定元素,而缺点是插入删除的效率较低(需要整体移动内部元素);链表的优点在于插入,删除元素时效率较高,但由于不支持随机访问,特定元素的查找效率为线性复杂度O(n),效率较低。

  向量和链表的优缺点是互补的,那么有没有办法兼具两者的优点呢?这便引出了接下来需要介绍的数据结构——二叉搜索树(Binary Search Tree)。

  二叉搜索树和链表类似,同样是以节点为单位存储数据的链式数据结构。二叉搜索树作为一种树形数据结构,内部维护着一个根节点,在插入新数据时,会不断的和当前子树的根节点进行key值的大小比较,较小的key值落在左子树,较大的key值落在右子树,使得二叉搜索树从左到右维持一个有序的状态。

形式化的定义:

  二叉搜索树的左子树上结点的值均小于根结点的值;右子树上结点的值均大于根结点的值;二叉搜索树的左、右子树也分别为二叉搜索树。

  由于二叉搜索树中的数据是有序存储的,可以使用高效的二分查找查询特定元素;同时由于内部存储结构为链式节点,在插入、删除元素时的效率和链表类似,也十分高效。

  可以说,二叉搜索树兼具了向量和链表的优点。

  

自己动手实现java数据结构(六)二叉搜索树

2.二叉搜索树ADT接口

  二叉搜索树同样是一个存储key/value类型数据结构,因此和哈希表实现共用同一个接口(Map)。K/V数据结构需要暴露出内部节点的Key,value给用户灵活的访问,但哈希表和二叉搜索树的内部节点实现有一定的差异,所以在Map接口中暴露了Map.EntryNode接口,由哈希表和二叉搜索树的内部节点分别实现Map.EntryNode接口。

public interface Map <K,V>{
    /**
     * 存入键值对
     * @param key   key值
     *  value value
     * @return 被覆盖的的value值
     */
    V put(K key,V value);

    
     * 移除键值对
     *  被删除的value的值
     
    V remove(K key);

    
     * 获取key对应的value值
     *       对应的value值
     
    V get(K key);

    
     * 是否包含当前key值
     *       true:包含 false:不包含
     */
    boolean containsKey(K key);

    
     * 是否包含当前value值
     *  value   value值
     *         true:包含 false:不包含
      containsValue(V value);

    
     * 获得当前map存储的键值对数量
     *  键值对数量
     * int size();

    
     * 当前map是否为空
     *   true:为空 false:不为空
      isEmpty();

    
     * 清空当前map
     void clear();

    
     * 获得迭代器
     *  迭代器对象
     
    Iterator<EntryNode<K,V>> iterator();

    
     * entry 键值对节点接口
     * interface EntryNode<K,1)">{
        
         * 获得key值
         * 
        K getKey();

        
         * 获得value值
         * 
        V getValue();

        
         * 设置value值
         * */
         setValue(V value);
    }
}

3.二叉搜索树实现细节

3.1?二叉搜索树基本属性

  值得一提的是,二叉搜索树通过给存储的元素进行排序来加快查询的速度(遍历查询 ---> 二分查询)。

  java是面向对象的语言,二叉搜索树中的元素不仅仅是整数、小数。如果说对于整数、小数甚至字符串的排序,我们确定了一个公认的排序逻辑。但是用户自定义的对象,例如小猫、小狗对象的排序可就仁者见仁智者见智了。

  由于java并不支持比较符号">","<"的运算符重载,因此我们提供了一个比较排序的接口,用户可以在二叉搜索树初始化时指定排序时元素间比较的逻辑,使得二叉搜索树能以满足用户需求的方式执行排序的逻辑。

比较器接口(Comparator)定义:

@FunctionalInterface
interface Comparator<T> {
    
     * 比较方法逻辑
     *  o1    参数1
     *  o2    参数2
     *       返回值大于0 ---> (o1 > o2)
     *              返回值等于0 ---> (o1 = o2)
     *              返回值小于0 ---> (o1 < o2)
      compare(T o1,T o2);
}

基本属性:

class TreeMap<K,V> implements Map<K,1)">{

    
     * 根节点
     * private EntryNode<K,1)"> root;

    
     * 比较器(初始化之后,不能改)
     * private final Comparator<? super K> comparator;

    
     * 当前二叉树的大小
     *  size;

    
     * 默认构造函数
     * public TreeMap() {
        this.comparator = null;
    }

    
     * 指定了比较器的构造函数
     * public TreeMap(Comparator<?  comparator) {
        this.comparator = comparator;
    }
}

3.2?二叉搜索树内部节点

  二叉搜索树的内部节点除了必须的key,value字段,同时还维护了左、右孩子节点和双亲节点的引用。

  通过实现暴露出去的Map.EntryNode接口,允许用户访问内部节点的key、value值,但二叉搜索树节点内部的孩子、双亲节点的引用是被封装起来的,外部用户是无法感知,也无需了解的。

   
     * 二叉搜索树 内部节点
     * static class EntryNode<K,1)">implements Map.EntryNode<K,1)">
         * key值
         * 
        K key;
        
        
         * value值
         * 
        V value;
        
        
         * 左孩子节点
         * 
        EntryNode<K,1)"> left;

        
         * 右孩子节点
         *  right;

        
         * 双亲节点
         *  parent;

        EntryNode(K key,V value) {
            this.key = key;
            this.value = value;
        }

        EntryNode(K key,V value,EntryNode<K,1)"> parent) {
             value;
            this.parent = parent;
        }

        @Override
         K getKey() {
            return key;
        }

        @Override
         V getValue() {
             value;
        }

        @Override
         setValue(V value) {
             String toString() {
            return key + "=" + value;
        }
    }

3.3?二叉搜索树 内部辅助函数

  为了简化代码逻辑以及去除重复代码,在实现过程中提取出了诸如:获取第一个节点(getFirst)、获取节点直接后继(getSuccessor)、获得key值对应目标节点(getTargetEntryNode)等等辅助方法。

  getTargetEntryNode用于获取key值对应的目标节点,运用了哨兵的思想。从根节点开始,使用二分查找的方式逐步逼近key值对应目标节点的位置。

  如果目标节点确实存在,自然直接返回目标节点的引用(相对位置:RelativePosition.CURRENT);

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章