数据结构之集合和映射

端碗吹水 2021-01-21 23:47:48
集合 数据结构 数据 结构 映射


基于二分搜索树的集合实现

集合(Set)的基础概念:

  • 数据结构中的集合概念与数学中的集合概念是一样的,集合中的元素是无序且不重复的,一个元素在集合中只会出现一次。集合在逻辑上是一个线性的结构,但在底层中可以采用多种实现,例如链表、二分搜索树及哈希表等。所以集合总的来说是高层次的抽象数据结构,底层实现可以有多种。

本小节演示一下如何基于二分搜索树实现一个集合,我们都知道二分搜索树通常不存放重复元素,且不采用中序遍历的情况下访问元素是“无序”的(但通常基于树实现的集合是有序集合),正好符合集合的特性,可以直接作为集合的底层实现。

首先,我们要实现一个简单的二分搜索树。具体代码如下:

package tree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* 二分搜索树
* 由于存储的数据需具有可比较性,所以泛型需继承Comparable接口
*
* @author 01
**/
public class BinarySearchTree<E extends Comparable<E>> {
/**
* 节点结构
*/
private class Node {
E e;
Node left;
Node right;
public Node() {
this(null, null, null);
}
public Node(E e) {
this(e, null, null);
}
public Node(E e, Node left, Node right) {
this.e = e;
this.left = left;
this.right = right;
}
}
/**
* 根节点
*/
private Node root;
/**
* 表示树里存储的元素个数
*/
private int size;
/**
* 获取树里的元素个数
*
* @return 元素个数
*/
public int size() {
return size;
}
/**
* 树是否为空
*
* @return 为空返回true,否则返回false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 向二分搜索树中添加一个新元素e
*
* @param e 新元素
*/
public void add(E e) {
if (root == null) {
// 根节点为空的处理
root = new Node(e);
size++;
} else {
add(root, e);
}
}
/**
* 向以node为根的二分搜索树中插入元素e,递归实现
*/
private void add(Node node, E e) {
// 递归的终止条件
if (e.equals(node.e)) {
// 不存储重复元素
return;
} else if (e.compareTo(node.e) < 0 && node.left == null) {
// 元素e小于node节点的元素,并且node节点的左孩子为空,所以成为node节点的左孩子
node.left = new Node(e);
size++;
return;
} else if (e.compareTo(node.e) > 0 && node.right == null) {
// 元素e大于node节点的元素,并且node节点的右孩子为空,所以成为node节点的右孩子
node.right = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) < 0) {
// 元素e小于node节点的元素,往左子树走
add(node.left, e);
} else {
// 元素e大于node节点的元素,往右子树走
add(node.right, e);
}
}
/**
* 从二分搜索树中删除元素为e的节点
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* 删除以node为根的二分搜索树中值为e的节点,递归实现
* 返回删除节点后新的二分搜索树的根
*/
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
// 要删除的节点在左子树中
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
// 要删除的节点在右子树中
node.right = remove(node.right, e);
return node;
}
// 找到了要删除的节点
// 待删除的节点左子树为空的情况
if (node.left == null) {
// 如果有右子树,需要将其挂到被删除的节点上
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// 待删除的节点右子树为空的情况
if (node.right == null) {
// 如果有左子树,需要将其挂到被删除的节点上
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// 待删除的节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
Node successor = minimum(node.right);
// 用这个节点替换待删除节点的位置
// 由于removeMin里已经维护过一次size了,所以这里就不需要维护一次了
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
/**
* 查看二分搜索树中是否包含元素e
*/
public boolean contains(E e) {
return contains(root, e);
}
/**
* 查看以node为根节点的二分搜索树中是否包含元素e,递归实现
*/
private boolean contains(Node node, E e) {
if (node == null) {
return false;
}
if (e.compareTo(node.e) == 0) {
return true;
} else if (e.compareTo(node.e) < 0) {
// 找左子树
return contains(node.left, e);
}
// 找右子树
return contains(node.right, e);
}
}

有了二分搜索树这个底层数据结构之后,实现集合就很简单了,因为二分搜索树基本可以覆盖集合的特性。由于集合是一个相对上层的数据结构,所以在实现集合时需要定义一个接口,抽象出集合的操作。这样底层无论使用什么数据结构实现,对于上层来说都是无感知的,这也是面向接口编程的好处。接口定义如下:

package set;
/**
* 集合接口
*
* @author 01
* @date 2021-01-18
**/
public interface Set<E> {
/**
* 添加元素
*
* @param e e
*/
void add(E e);
/**
* 删除元素
*
* @param e e
*/
void remove(E e);
/**
* 是否包含指定元素
*
* @param e e
* @return boolean
*/
boolean contains(E e);
/**
* 获取集合中的元素个数
*
* @return int
*/
int getSize();
/**
* 集合是否为空
*
* @return boolean
*/
boolean isEmpty();
}

在集合接口的具体实现类中,基本只需要调用二分搜索树的方法即可,这样我们很简单就实现了一个集合数据结构。代码如下:

package set;
import tree.BinarySearchTree;
/**
* 基于二分搜索树实现的集合
*
* @author 01
* @date 2021-01-18
**/
public class TreeSet<E extends Comparable<E>> implements Set<E> {
private final BinarySearchTree<E> bst;
public TreeSet() {
bst = new BinarySearchTree<>();
}
@Override
public void add(E e) {
bst.add(e);
}
@Override
public void remove(E e) {
bst.remove(e);
}
@Override
public boolean contains(E e) {
return bst.contains(e);
}
@Override
public int getSize() {
return bst.size();
}
@Override
public boolean isEmpty() {
return bst.isEmpty();
}
}

基于链表的集合实现

使用其他数据结构,例如链表也能实现集合,同为线性结构的动态数组也可以。本小节简单演示下,基于基于链表的集合实现。和之前一样,首先实现一个简单的链表数据结构,代码如下:

package linkedlist;
/**
* 单向链表数据结构
*
* @author 01
* @date 2018-11-08
**/
public class LinkedList<E> {
/**
* 链表中的节点
*/
private class Node {
E e;
Node next;
public Node() {
this(null, null);
}
public Node(E e) {
this(e, null);
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
@Override
public String toString() {
return e.toString();
}
}
/**
* 虚拟头节点
*/
private Node dummyHead;
/**
* 链表中元素的个数
*/
private int size;
public LinkedList() {
this.dummyHead = new Node(null, null);
this.size = 0;
}
/**
* 获取链表中的元素个数
*
* @return 元素个数
*/
public int getSize() {
return size;
}
/**
* 链表是否为空
*
* @return 为空返回true,否则返回false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在链表的index(0-based)位置添加新的元素e
*
* @param index 元素添加的位置
* @param e 新的元素
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node prev = dummyHead;
// 移动prev到index前一个节点的位置
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
// 同样,以上三句代码可以一句代码完成
// prev.next = new Node(e, prev.next);
size++;
}
/**
* 在链表头添加新的元素e
*
* @param e 新的元素
*/
public void addFirst(E e) {
add(0, e);
}
/**
* 查找链表中是否包含元素e
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
// 第一种遍历链表的方式
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* 从链表中删除元素e
*/
public void removeElement(E e) {
Node prev = dummyHead;
while (prev.next != null) {
if (prev.next.e.equals(e)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
}
}
}

然后基于这个链表结构就可以轻易实现集合了。代码如下:

package set;
import linkedlist.LinkedList;
/**
* 基于链表实现的集合
*
* @author 01
* @date 2021-01-18
**/
public class LinkedListSet<E> implements Set<E> {
private final LinkedList<E> linkedList;
public LinkedListSet() {
linkedList = new LinkedList<>();
}
@Override
public void add(E e) {
// 不存储重复元素
if (!linkedList.contains(e)) {
linkedList.addFirst(e);
}
}
@Override
public void remove(E e) {
linkedList.removeElement(e);
}
@Override
public boolean contains(E e) {
return linkedList.contains(e);
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
}

映射基础

映射(Map)在数据结构中是指一种key-value的数据结构,key与value是有具有一对一关系的,所以称之为映射。这与数学中的映射概念一样,定义域与值域具有一对一的映射关系,描述这个映射关系的是函数:

映射这个词相对来说有些晦涩,我们也可以将其类比成字典,这也是为什么一些编程语言中将其称为字典(通常缩写为dict)的原因。因为字典就是一种典型的映射关系,一个词对应着一个释义,也是key-value的结构,通过key我们就能快速找到value。

其实映射在我们的日常生活中无处不在,例如,身份证 -> 人、车牌号 -> 车以及工牌 -> 员工等。所以Map在很多领域都有着很重要的作用,最典型的就是大数据领域中的核心思想:Map-Reduce,典型的应用就是词频统计:单词 -> 频率。

与集合一样,映射也是一个相对上层的数据结构,底层也可以由多种不同的数据结构来实现,常见的底层实现有:链表、二分搜索树、红黑树以及哈希表等。所以我们需要定义一个Map接口作为上层抽像:

package map;
/**
* 映射接口
*
* @author 01
* @date 2021-01-18
**/
public interface Map<K, V> {
/**
* 添加元素
*
* @param key 键
* @param value 值
*/
void add(K key, V value);
/**
* 根据key删除元素
*
* @param key 键
* @return 被删除的value
*/
V remove(K key);
/**
* 根据key查询元素是否存在
*
* @param key key
* @return boolean
*/
boolean contains(K key);
/**
* 根据key获取value
*
* @param key key
* @return value
*/
V get(K key);
/**
* 改变key的value
*
* @param key key
* @param value value
*/
void set(K key, V value);
/**
* 获取Map中的元素个数
*
* @return 元素个数
*/
int getSize();
/**
* 判断Map是否为空
*
* @return boolean
*/
boolean isEmpty();
}

基于链表的映射实现

使用链表来实现映射,与实现普通的链表差别不大,唯一不同的就是链表中的节点不再是简单地存储单个元素,而是需要有两个成员变量分别存储key和value。具体的实现代码如下:

package map;
/**
* 基于链表实现的Map
*
* @author 01
* @date 2021-01-18
*/
public class LinkedListMap<K, V> implements Map<K, V> {
/**
* 链表的节点结构,节点中会存储键值对,而不是单个元素
*/
private class Node {
public K key;
public V value;
public Node next;
public Node(K key, V value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
public Node(K key, V value) {
this(key, value, null);
}
public Node() {
this(null, null, null);
}
@Override
public String toString() {
return key.toString() + " : " + value.toString();
}
}
/**
* 虚拟头节点
*/
private final Node dummyHead;
private int size;
public LinkedListMap() {
dummyHead = new Node();
size = 0;
}
/**
* 根据传入的key获取链表中的节点
*/
private Node getNode(K key) {
Node cur = dummyHead.next;
while (cur != null) {
if (cur.key.equals(key)) {
return cur;
}
cur = cur.next;
}
return null;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public boolean contains(K key) {
return getNode(key) != null;
}
@Override
public V get(K key) {
Node node = getNode(key);
return node == null ? null : node.value;
}
@Override
public void add(K key, V value) {
Node node = getNode(key);
if (node == null) {
// key不存在,往链表的头部插入新元素
dummyHead.next = new Node(key, value, dummyHead.next);
size++;
} else {
// 否则,改变value
node.value = value;
}
}
@Override
public void set(K key, V newValue) {
Node node = getNode(key);
if (node == null) {
throw new IllegalArgumentException(key + " doesn't exist!");
}
node.value = newValue;
}
@Override
public V remove(K key) {
Node prev = dummyHead;
// 根据key找到待删除节点的前一个节点
while (prev.next != null) {
if (prev.next.key.equals(key)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
// 删除目标节点
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
}
return null;
}
}

基于二分搜索树的映射实现

最后,我们来看一下基于二分搜索树的映射实现。看了之前基于链表的实现案例后,对本小节的内容就很容易理解了,因为基于二分搜索树的映射实现也是一样的,除了树的节点结构不一样外,其余的逻辑与普通的二分搜索树没啥太大区别。具体实现代码如下:

package map;
/**
* 基于二分搜索树实现的Map
*
* @author 01
* @date 2021-01-18
*/
public class TreeMap<K extends Comparable<K>, V> implements Map<K, V> {
/**
* 二分搜索树的节点结构,节点中会存储键值对,而不是单个元素
*/
private class Node {
public K key;
public V value;
public Node left, right;
public Node(K key, V value) {
this.key = key;
this.value = value;
left = null;
right = null;
}
}
private Node root;
private int size;
public TreeMap() {
root = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void add(K key, V value) {
// 向二分搜索树中添加新的元素(key, value)
root = add(root, key, value);
}
/**
* 向以node为根的二分搜索树中插入元素(key, value),递归实现
*
* @return 返回插入新节点后二分搜索树的根
*/
private Node add(Node node, K key, V value) {
if (node == null) {
size++;
return new Node(key, value);
}
if (key.compareTo(node.key) < 0) {
node.left = add(node.left, key, value);
} else if (key.compareTo(node.key) > 0) {
node.right = add(node.right, key, value);
} else {
node.value = value;
}
return node;
}
/**
* 返回以node为根节点的二分搜索树中,key所在的节点
*/
private Node getNode(Node node, K key) {
if (node == null) {
return null;
}
if (key.equals(node.key)) {
return node;
} else if (key.compareTo(node.key) < 0) {
return getNode(node.left, key);
} else {
return getNode(node.right, key);
}
}
@Override
public boolean contains(K key) {
return getNode(root, key) != null;
}
@Override
public V get(K key) {
Node node = getNode(root, key);
return node == null ? null : node.value;
}
@Override
public void set(K key, V newValue) {
Node node = getNode(root, key);
if (node == null) {
throw new IllegalArgumentException(key + " doesn't exist!");
}
node.value = newValue;
}
/**
* 返回以node为根的二分搜索树的最小值所在的节点
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* 删除掉以node为根的二分搜索树中的最小节点
* 返回删除节点后新的二分搜索树的根
*/
private Node removeMin(Node node) {
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
node.left = removeMin(node.left);
return node;
}
@Override
public V remove(K key) {
Node node = getNode(root, key);
if (node != null) {
// 从二分搜索树中删除键为key的节点
root = remove(root, key);
return node.value;
}
return null;
}
private Node remove(Node node, K key) {
if (node == null) {
return null;
}
if (key.compareTo(node.key) < 0) {
node.left = remove(node.left, key);
return node;
} else if (key.compareTo(node.key) > 0) {
node.right = remove(node.right, key);
return node;
} else {
// 待删除节点左子树为空的情况
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// 待删除节点右子树为空的情况
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// 待删除节点左右子树均不为空的情况
// 找到比待删除节点大的最小节点,即待删除节点右子树的最小节点
Node successor = minimum(node.right);
// 用这个节点顶替待删除节点的位置
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

版权声明
本文为[端碗吹水]所创,转载请带上原文链接,感谢
https://cloud.tencent.com/developer/article/1777864

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云