成都网站建设公,网站建设必须要备案吗,公司网站内容规划,阳江房产网最新楼盘精装修登神长阶 第八神装 TreeSet 第九神装 TreeMap 目录
#x1f489; 一.二叉搜索树
#x1fa78;1. 定义
#x1f48a;2. 基本操作
#x1fa79;3. 插入操作
#x1fa7c;4. 查找操作
#x1fa7a;5. 删除操作*
#x1fa7b;6. 遍历操作
#x1fa92;7.性能分析 … 登神长阶 第八神装 TreeSet 第九神装 TreeMap 目录 一.二叉搜索树
1. 定义
2. 基本操作
3. 插入操作
4. 查找操作
5. 删除操作*
6. 遍历操作
7.性能分析
二.TreeSet
1. 定义 2.操作
3. Set主要特性
4. TreeSet的内部实现
5. 应用场景
三.TreeMap
1.定义
2.操作
3.Map的主要特性
4. TreeMap的内部实现
5.应用场景
四.总结与反思 一.二叉搜索树
首先我们要知道TreeSet/TreeMap底层都采用的都是一种二叉搜索树也叫自平衡二叉树因此我们先来了解一下二叉搜索树。
对于他的学习若之前没有了解的可以参考Java 【数据结构】 二叉树Binary_Tree【神装】
1. 定义
二叉搜索树Binary Search Tree简称BST是一种特殊的二叉树它具有以下性质
每个节点都有一个键Key和两个指向其他节点的指针左子指针和右子指针。任意节点的左子树中的所有键都小于该节点的键。任意节点的右子树中的所有键都大于该节点的键。左右子树也都是二叉搜索树。不存在键值相等的节点。 在Java中我们可以这样定义一个二叉搜索树
public class BinarySearchTree {private class Node {int val;Node left;Node right;Node(int val) {this.val val;left null;right null;}}private Node root;// 构造函数、插入方法、查找方法、删除方法等...
}2. 基本操作
二叉搜索树支持以下基本操作
插入Insert向树中插入一个新节点保持树的二叉搜索性质。查找Search在树中查找一个特定的节点。删除Delete从树中删除一个节点并保持树的二叉搜索性质。遍历Traverse对树进行遍历常用的遍历方式有前序、中序和后序遍历。 接下来我们详细介绍一下它的各个操作因为后续二叉树本身是数据结构中一个很关键的知识点像红黑树AVL树等等我们需要牢牢掌握 3. 插入操作
插入操作的步骤如下
创建新节点。比较新节点的键与根节点的键 如果新节点的键小于根节点的键则将新节点插入到根节点的左子树中。如果新节点的键大于根节点的键则将新节点插入到根节点的右子树中。如果插入点是空则直接在新位置插入新节点。如果插入点非空则递归地在相应子树中进行插入操作。 代码: /*** 插入一个元素* param key*/public void insert(int key) {TreeNode nodenew TreeNode(key);//若该搜索树为空则直接作为根节点if (rootnull){rootnode;}TreeNode curroot;TreeNode parentnull;while(cur!null){if (cur.keykey){parent cur;curcur.right;}else if(cur.keykey){parent cur;curcur.left;}else{return ;}}if (parent.keykey){parent.leftnode;}else{parent.rightnode;}}
4. 查找操作
查找操作的步骤如下
从根节点开始比较。如果查找的键小于当前节点的键则递归地在左子树中查找。如果查找的键大于当前节点的键则递归地在右子树中查找。如果找到节点则返回该节点。如果没有找到则返回null。 代码 //查找key是否存在public TreeNode search(int key) {TreeNode cur root;while(cur!null){if (cur.keykey){curcur.right;}else if(cur.keykey){curcur.left;}else{return cur;}}return null;}
5. 删除操作* 设待删除结点为 cur, 待删除结点的双亲结点为 parent 1. cur.left null cur 是 root则 root cur.right cur 不是 rootcur 是 parent.left则 parent.left cur.right cur 不是 rootcur 是 parent.right则 parent.right cur.right 2. cur.right null cur 是 root则 root cur.left cur 不是 rootcur 是 parent.left则 parent.left cur.leftcur 不是 rootcur 是 parent.right则 parent.right cur.left 3. cur.left ! null cur.right ! null 需要使用替换法进行删除即在它的右子树中寻找中序下的第一个结点(关键码最小)用它的值填补到被删除节点中再来处理该结点的删除问题 代码 //删除key的值public boolean remove(int key) {TreeNode cur root;TreeNode parentnull;while(cur!null){if (cur.keykey){parentcur;curcur.left;}else if (cur.keykey){parentcur;curcur.right;}else{removeNode(parent,cur);return true;}}return false;}public void removeNode(TreeNode parent,TreeNode cur){if (cur.leftnull){//左子树为空if (curroot){rootcur.right;}else if(curparent.left){parent.leftcur.right;}else{parent.rightcur.right;}}else if (cur.rightnull){//右子树为空if (curroot){rootcur.left;}else if (curparent.left){parent.leftcur.left;}else{parent.rightcur.left;}}else{//左右子树都不为空 右子树的最小值代替TreeNode targetpcur;TreeNode targetcur.right;while(target!null){targetptarget;targettarget.left;}cur.keytarget.key;//删除原本数值if (targetp.lefttarget){targetp.lefttarget.left;}else{targetp.righttarget.right;}}} 6. 遍历操作
二叉搜索树的遍历操作与普通二叉树相同可以使用前序、中序和后序遍历。 中序遍历会按照从小到大的顺序访问所有节点是一个有序数列 前序遍历代码举例 public void prevOreder(TreeNode root){if (rootnull){return;}prevOreder(root.left);System.out.print(root.key );prevOreder(root.right);}
其余遍历方式包括非递归的遍历方式 Java 【数据结构】 二叉树Binary_Tree【神装】
7.性能分析 插入和删除操作都必须先查找查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树若每个元素查找的概率相等则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数即结点越深则比较次数越多。 但对于同一个关键码集合如果各关键码插入的次序不同可能得到不同结构的二叉搜索树 最优情况下二叉搜索树为完全二叉树其平均比较次数为log N 最差情况下二叉搜索树退化为单支树其平均比较次数为N/2 二.TreeSet
1. 定义
TreeSet是Java集合框架中的一种有序集合它实现了Set接口因此具有不允许重复元素的特性。与HashSet不同TreeSet使用红黑树数据结构来存储元素这使得元素在集合中保持有序。 2.操作 方法 解释 boolean add (E e) 添加元素但重复元素不会被添加成功 void clear () 清空集合 boolean contains (Object o) 判断 o 是否在集合中 IteratorE iterator () 返回迭代器 boolean remove (Object o) 删除集合中的 o int size() 返回 set 中元素的个数 boolean isEmpty() 检测 set 是否为空空返回 true 否则返回 false Object[] toArray() 将 set 中的元素转换为数组返回 boolean containsAll(Collection? c) 集合 c 中的元素是否在 set 中全部存在是返回 true 否则返回 false boolean addAll(Collection? extends E c) 将集合 c 中的元素添加到 set 中可以达到去重的效果
import java.util.TreeSet;public class TreeSetExample {public static void main(String[] args) {// 创建一个TreeSet元素自然排序升序TreeSetInteger numbers new TreeSet();// 添加一些元素numbers.add(5);numbers.add(3);numbers.add(8);numbers.add(1);// 打印整个TreeSetSystem.out.println(TreeSet: numbers);// 查找是否存在某个元素System.out.println(Contains 6: numbers.contains(6));// 删除一个元素numbers.remove(3);System.out.println(TreeSet after removing 3: numbers);// 遍历TreeSetSystem.out.println(Traversing TreeSet:);for (int number : numbers) {System.out.println(number);}// 排序和检索操作System.out.println(First element: numbers.first());System.out.println(Last element: numbers.last());System.out.println(Element greater than 4: numbers.higher(4));System.out.println(Element lower than 4: numbers.lower(4));}
}3. Set主要特性
Set是继承自Collection的一个接口类 TreeSet 中不能插入 null 的 key HashSet 可以。 实现 Set 接口的常用类有 TreeSet 和 HashSet 还有一个 LinkedHashSet LinkedHashSet 是在 HashSet 的基础上维护了一个双向链表来记录元素的插入次序。 有序性元素按照自然顺序或者根据提供的Comparator进行排序。当向TreeSet中添加元素时会根据元素之间的比较关系进行自动排序。不可重复性TreeSet中的元素不允许重复。Set最大的功能就是对集合中的元素进行去重 基于红黑树实现通过红黑树数据结构实现了有序的、唯一元素存储。 Set 底层结构 TreeSet 底层结构 红黑树 插入 / 删除 / 查找时间 复杂度 O(log N) 是否有序 关于 Key 有序 线程安全 不安全 插入 / 删除 / 查找区别 按照红黑树的特性来进行插入和删除 比较与覆写 key 必须能够比较否则会抛出 ClassCastException 异常 应用场景 需要 Key 有序场景下
4. TreeSet的内部实现
TreeSet通过红黑树Red-Black Tree数据结构实现了有序的、唯一元素存储。红黑树是一种自平衡的二叉查找树在插入和删除操作后能够保持相对较低的高度从而保证了检索、插入和删除操作的时间复杂度为O(log n)。
5. 应用场景
TreeSet适用于需要保持元素有序并且去除重复元素的场景。由于其基于红黑树实现可以高效地支持元素的查找、插入和删除操作。因此在需要有序集合且不允许重复元素的情况下TreeSet是一个十分实用的选择。总而言之
当需要保持元素的有序性且不允许重复时TreeSet是一个很好的选择。常用于需要按照特定顺序处理元素的情况。
三.TreeMap
1.定义 TreeMap是基于红黑树数据结构的键值对映射。它保证键的有序性键按照其自然顺序通过键的compareTo方法确定的顺序进行排序。 2.操作 方法 解释 V get (Object key) 返回 key 对应的 value V getOrDefault (Object key, V defaultValue) 返回 key 对应的 value key 不存在返回默认值 V put (K key, V value) 设置 key 对应的 value V remove (Object key) 删除 key 对应的映射关系 SetK keySet () 返回所有 key 的不重复集合 CollectionV values () 返回所有 value 的可重复集合 SetMap.EntryK, V entrySet () 返回所有的 key-value 映射关系 boolean containsKey (Object key) 判断是否包含 key boolean containsValue (Object value) 判断是否包含 value import java.util.Map;
import java.util.TreeMap;public class TreeMapExample {public static void main(String[] args) {// 创建一个 TreeMapTreeMapInteger, String treeMap new TreeMap();// 向 TreeMap 中添加键值对treeMap.put(1, value1);treeMap.put(2, value2);treeMap.put(3, value3);treeMap.put(4, value4);treeMap.put(5, value5);// 打印 TreeMapSystem.out.println(TreeMap: treeMap);// 获取一个键对应的值String value treeMap.get(3);System.out.println(Value for key 3: value);// 删除一个键值对boolean removed treeMap.remove(2);System.out.println(Remove key 2: removed);// 获取 TreeMap 的大小int size treeMap.size();System.out.println(Size of TreeMap: size);// 检查 TreeMap 是否为空boolean isEmpty treeMap.isEmpty();System.out.println(Is TreeMap empty: isEmpty);// 遍历 TreeMapfor (Map.EntryInteger, String entry : treeMap.entrySet()) {System.out.println(Key: entry.getKey() , Value: entry.getValue());}}
}3.Map的主要特性 Map是一个接口不能直接实例化对象如果要实例化对象只能实例化其实现类TreeMap或者HashMap Map中存放键值对的Key是唯一的value是可以重复的 在TreeMap中插入键值对时key不能为空否则就会抛NullPointerException异常value可以为空。但是HashMap的key和value都可以为空。 Map中的Key可以全部分离出来存储到Set中来进行访问(因为Key不能重复)。 Map中的value可以全部分离出来存储在Collection的任何一个子集合中(value可能有重复)。 Map中键值对的Key不能直接修改value可以修改如果要修改key只能先将该key删除掉然后再来进行重新插入。 Map底层结构 TreeMap 底层结构 红黑树 插入 / 删除 / 查找时间 复杂度 O(log N) 是否有序 关于 Key 有序 线程安全 不安全 插入 / 删除 / 查找区别 需要进行元素比较 比较与覆写 key 必须能够比较否则会抛出 ClassCastException 异常 应用场景 需要 Key 有序场景下 4. TreeMap的内部实现
TreeMap的内部实现是通过红黑树来存储键值对的。红黑树是一种自平衡的二叉查找树它保证了在插入和删除操作后树的高度保持相对较低从而保证了高效的查找、插入和删除操作。
5.应用场景
在实际应用中如果你需要一个有序的映射表并且不允许键重复那么TreeMap是一个很好的选择。它既满足了有序性的需求又提供了高效的操作性能。总而言之
当需要保持键的有序性且需要根据键快速查找值时TreeMap是一个很好的选择。常用于需要按照特定顺序处理键值对的情况。
四.总结与反思 人们在一起可以做出单独一个人所不能做出的事业智慧双手力量结合在一起几乎是万能的。——韦伯斯特 在学习二叉搜索树和TreeSet/TreeMap的过程中我深刻体会到了数据结构在编程中的应用和重要性。二叉搜索树作为一种特殊的二叉树其特性包括每个节点的左子树都比当前节点小右子树都比当前节点大这使得在二叉搜索树中进行查找、插入和删除操作的时间复杂度可以达到O(log n)相比于线性搜索的O(n)有了显著的提升。而TreeSet和TreeMap的底层实现正是基于这种高效的数据结构——红黑树。 红黑树是一种自平衡的二叉查找树它通过红黑规则来保持树的平衡确保任何节点的左子树的高度最多比右子树高1从而保证了树的平衡性。在TreeSet和TreeMap中插入、删除和查找操作的时间复杂度均为O(log n)这使得它们在处理大量数据时依然能够保持高效。 学习二叉搜索树和TreeSet/TreeMap的过程中我认识到数据结构的选择对于程序的性能有着至关重要的影响。虽然HashMap在查找、插入和删除操作上提供了O(1)的时间复杂度但是它不保证元素的顺序而TreeSet和TreeMap在保持有序的同时牺牲了一部分时间复杂度。在实际应用中我们需要根据具体需求选择合适的数据结构以达到最优的性能。 此外在学习过程中我也意识到了在多线程环境中使用TreeMap时需要注意同步问题。TreeMap不是线程安全的如果需要在多线程环境中使用需要程序员手动同步或者通过包装等方式将TreeMap变成同步的。 总的来说学习二叉搜索树和TreeSet/TreeMap让我对数据结构和算法有了更深入的理解也让我认识到在实际编程中选择合适的数据结构的重要性。在未来的学习和工作中我会继续探索和运用这些知识以提高程序的性能和可靠性。 以上就是本期的全部内容啦若有错误疏忽希望各位大佬及时指出 制作不易希望能对各位提供微小的帮助可否留下你免费的赞呢
