首页 > 其他分享 >TreeMap

TreeMap

时间:2023-11-02 13:11:06浏览次数:39  
标签:TreeMap value 查找 key put 节点

TreeMap是Map家族中的一员,也是用来存放key-value键值对的。平时在工作中使用的可能并不多,它最大的特点是遍历时是有顺序的,根据key的排序规则来
TreeMap是一个双列集合,是Map的子类。底层由红黑树结构构成。

TreeMap是一个基于key有序的key value散列表。

  • map根据其键的自然顺序排序,或者根据map创建时提供的Comparator排序
  • 不是线程安全的
  • key 不可以存入null
  • 底层是基于红黑树实现的

特点:

  • 元素中键不能重复
  • 元素会按照大小顺序排序

image
以上是TreeMap的类结构图:

  • 实现了NavigableMap接口,NavigableMap又实现了Map接口,提供了导航相关的方法。
  • 继承了AbstractMap,该方法实现Map操作的骨干逻辑。
  • 实现了Cloneable接口,标记该类支持clone方法复制
  • 实现了Serializable接口,标记该类支持序列化
package com.hankcs.book.ch02;

import java.util.Map;
import java.util.TreeMap;

public class TreeTest {
    public static void main(String[] args) {

        Map<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(16, "a");
        treeMap.put(1, "b");
        treeMap.put(4, "c");
        treeMap.put(3, "d");
        treeMap.put(8, "e");
        // 遍历
        System.out.println("默认排序:");
        treeMap.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });

        // 构造方法传入比较器
        Map<Integer, String> tree2Map = new TreeMap<>((o1, o2) -> o2 - o1);
        tree2Map.put(16, "a");
        tree2Map.put(1, "b");
        tree2Map.put(4, "c");
        tree2Map.put(3, "d");
        tree2Map.put(8, "e");
        // 遍历
        System.out.println("倒序排序:");
        tree2Map.forEach((key, value) -> {
            System.out.println("key: " + key + ", value: " + value);
        });
    }
}

输出:

默认排序:
key: 1, value: b
key: 3, value: d
key: 4, value: c
key: 8, value: e
key: 16, value: a
倒序排序:
key: 16, value: a
key: 8, value: e
key: 4, value: c
key: 3, value: d
key: 1, value: b

实现原理

了解一下红黑树的特点:红黑树是一颗自平衡的排序二叉树。先从二叉树开始说起。

二叉树

image

就是每个结点的值按照大小排列的二叉树,二叉查找树方便对结点的值进行查找

特点

  • 节点的左子树小于节点本身;
  • 节点的右子树大于节点本身;
  • 左右子树同样为二叉搜索树;
  • 没有相等的结点;

二叉查找树的查找操作
查找方式:

从根结点开始,如果要查找的数据等于结点的值, 那就返回。
如果要查找的数据小于结点的值,那就在左子树中递归查找;
如果要查找的数据大于结点的值,那就在右子树中递归查找。

红黑树

image
它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目

特点

  • 每个节点都只能是红色或者黑色;
  • 根节点必为黑色;
  • 每个叶节点(NIL节点,空节点)是黑色的。
  • 连接红色节点的两个子节点都为黑色(红黑树不会出现相邻的红色节点);
  • 从任意节点出发,到其每个叶子节点的路径中包含相同数量的黑色节点;
  • 新加入到红黑树的节点为红色节点;

红黑树自平衡基本操作:

  • 变色:在不违反上述红黑树规则特点情况下,将红黑树某个node节点颜色由红变黑,或者由黑变红;
  • 左旋:逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点
  • 右旋:顺时针旋转两个节点,让一个节点被其左子节点取代,而该节点成为左子节点的右子节点

https://www.cnblogs.com/LiaHon/p/11203229.html

标签:TreeMap,value,查找,key,put,节点
From: https://www.cnblogs.com/vipsoft/p/17800136.html

相关文章

  • 界面控件DevExpress WPF TreeMap,轻松可视化复杂的分层结构数据!
    DevExpressWPF TreeMap控件允许用户使用嵌套的矩形块可视化复杂的平面或分层结构数据。P.S:DevExpressWPF拥有120+个控件和库,将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpressWPF能创建有着强大互动功能的XAML基础应用程序,这些应用程序专注于当代客户的......
  • HashMap、LinkedHashMap和TreeMap:你真的了解它们吗?
    亲爱的小伙伴们,大家好呀!我是小米,一个热衷于技术分享的90后程序员。今天我要和大家聊聊一个在面试中经常会被问到的话题:HashMap、LinkedHashMap、TreeMap的区别。这可是一个非常重要的知识点,不仅在面试中会被频繁提及,而且在实际开发中也经常用到。让我们一起深入了解这三者的异同吧!H......
  • Java TreeMap 介绍与使用
    介绍TreeMap是Java集合框架中的一个类,它实现了SortedMap接口,可以存储键值对,并按照键的自然顺序或者指定的比较器进行排序。TreeMap的底层是一棵红黑树,这是一种自平衡的二叉搜索树,可以保证在插入,删除,查找等操作中的时间复杂度为O(logn)。使用要使用TreeMap,我们需要导入......
  • TreeMap
    TreeMap的使用publicstaticvoidmain(String[]args){ TreeMap<String,Integer>map=newTreeMap<>(); //添加元素 Integerput1=map.put("大文",25); Integerput2=map.put("小文",26); Integerput3=map.put("小王",......
  • Map系列集合:TreeMap集合的原理、使用
        ......
  • java treemap
    TreeMap是Java中的一个类,它实现了Map接口,利用红黑树数据结构来有序存储键值对。TreeMap中的键按升序排序,若要自定义排序方式,则可以提供自定义的比较器。TreeMap实现了高效的数据访问、插入和删除操作,大多数常规操作的时间复杂度为O(logn)。importjava.util.TreeMap;public......
  • Java-Day-19( 对集合实现类的选择 + TreeSet + TreeMap )
    Java-Day-19总结-开发中如何选择集合实现类在开发中,选择什么集合实现类,主要取决于业务操作特点,然后根据集合实现类特性进行选择先判断存储的类型(一组对象或一组键值对)一组对象(单列):Collection接口允许重复:List增删多:LinkedList[底层维护了一个双向链......
  • 如何决定使用 HashMap 还是 TreeMap?
    @[toc]问:如何决定使用HashMap还是TreeMap?介绍TreeMap<k,v>的Key值是要求实现java.lang.Comparable,所以迭代的时候TreeMap默认是按照Key值升序排序的;TreeMap的实现是基于红黑树结构。适用于按自然顺序或自定义顺序遍历键(key)。HashMap<k,v>的Key值实现散列hashCode(),分布是散列的......
  • echarts treemap当份额太小时文字显示不全,解决为垂直显示全部文字
    before:after:解决: ......
  • Map - TreeSet & TreeMap 源码解析
    Java7-TreeSet&TreeMap总体介绍前者仅仅是对后者做了一层包装,也就是说TreeSet里面有一个TreeMap(适配器模式)。因此本文将重点分析TreeMap。JavaTreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序,key大小的评判可以通过其本身的自然顺序(natu......