Set and mapping of data structure

Blow water in a bowl 2021-01-21 23:56:39
set mapping data structure


Set implementation based on binary search tree

aggregate (Set) The basic concept of :

  • The concept of set in data structure is the same as that in mathematics , The elements in a set are unordered and do not repeat , An element only appears once in the collection . A set is logically a linear structure , But at the bottom, there are multiple implementations , Such as the list 、 Binary search tree and hash table, etc . So collections are generally high-level abstract data structures , There can be many underlying implementations .

This section demonstrates how to implement a collection based on a binary search tree , We all know that binary search trees don't usually store duplicate elements , And without using middle order traversal, accessing elements is “ disorder ” Of ( But usually the set based on tree implementation is an ordered set ), It just fits the properties of the set , It can be directly implemented as the bottom layer of the collection .

First , We want to achieve a simple Binary search tree . The specific code is as follows :

package tree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
/**
* Binary search tree
* Because the stored data needs to be comparable , So generics need to be inherited Comparable Interface
*
* @author 01
**/
public class BinarySearchTree<E extends Comparable<E>> {
/**
* The node structure
*/
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;
}
}
/**
* The root node
*/
private Node root;
/**
* Represents the number of elements stored in the tree
*/
private int size;
/**
* Get the number of elements in the tree
*
* @return Element number
*/
public int size() {
return size;
}
/**
* Is the tree empty
*
* @return Empty return true, Otherwise return to false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Add a new element to the binary search tree e
*
* @param e The new element
*/
public void add(E e) {
if (root == null) {
// The root node is empty
root = new Node(e);
size++;
} else {
add(root, e);
}
}
/**
* to node Insert elements for the binary search tree of the root e, Recursive implementation
*/
private void add(Node node, E e) {
// The termination condition of recursion
if (e.equals(node.e)) {
// Do not store duplicate elements
return;
} else if (e.compareTo(node.e) < 0 && node.left == null) {
// Elements e Less than node Element of node , also node The left child of the node is empty , So become node Node's left child
node.left = new Node(e);
size++;
return;
} else if (e.compareTo(node.e) > 0 && node.right == null) {
// Elements e Greater than node Element of node , also node The right child of the node is empty , So become node Node's right child
node.right = new Node(e);
size++;
return;
}
if (e.compareTo(node.e) < 0) {
// Elements e Less than node Element of node , Go to the left tree
add(node.left, e);
} else {
// Elements e Greater than node Element of node , Go to the right tree
add(node.right, e);
}
}
/**
* Remove the element from the binary search tree as e The node of
*/
public void remove(E e) {
root = remove(root, e);
}
/**
* Delete with node The median value of the binary search tree for the root is e The node of , Recursive implementation
* Returns the root of the new binary search tree after the node is deleted
*/
private Node remove(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
// The node to be deleted is in the left subtree
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
// The node to be deleted is in the right subtree
node.right = remove(node.right, e);
return node;
}
// The node to delete was found
// The left subtree of the node to be deleted is empty
if (node.left == null) {
// If I have a right subtree , It needs to be attached to the deleted node
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// When the right subtree of the node to be deleted is empty
if (node.right == null) {
// If I have a left subtree , It needs to be attached to the deleted node
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// The left and right subtrees of the node to be deleted are not empty
// Find the smallest node larger than the node to be deleted , That is, the smallest node of the right subtree of the node to be deleted
Node successor = minimum(node.right);
// Replace the position of the node to be deleted with this node
// because removeMin It's been maintained once in the library size 了 , So there's no need to maintain it once
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
/**
* See if there are elements in the binary search tree e
*/
public boolean contains(E e) {
return contains(root, e);
}
/**
* View to node Whether there are elements in the binary search tree for the root node e, Recursive implementation
*/
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) {
// Look for zuozhu
return contains(node.left, e);
}
// Look for the right subtree
return contains(node.right, e);
}
}

With the binary search tree as the underlying data structure , It's easy to implement collections , Because the binary search tree can basically cover the characteristics of the set . Because a set is a relatively upper level data structure , So when you implement a collection, you need to define an interface , Abstract the operation of a set . In this way, no matter what data structure the underlying layer uses to implement , For the upper class, it's all senseless , This is also the benefit of interface oriented programming . The interface is defined as follows :

package set;
/**
* Collection interface
*
* @author 01
* @date 2021-01-18
**/
public interface Set<E> {
/**
* Additive elements
*
* @param e e
*/
void add(E e);
/**
* Remove elements
*
* @param e e
*/
void remove(E e);
/**
* Whether to include the specified element
*
* @param e e
* @return boolean
*/
boolean contains(E e);
/**
* Get the number of elements in the collection
*
* @return int
*/
int getSize();
/**
* Whether the set is empty
*
* @return boolean
*/
boolean isEmpty();
}

In the concrete implementation class of the collection interface , Basically, you just need to call the binary search tree method , In this way, we simply implement a set data structure . The code is as follows :

package set;
import tree.BinarySearchTree;
/**
* Set based on binary search tree implementation
*
* @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();
}
}

Set implementation based on linked list

Use other data structures , For example, linked lists can also implement collections , Dynamic arrays with linear structure can also . This section simply demonstrates , Set implementation based on linked list . Same as before , First, implement a simple Linked list data structure , The code is as follows :

package linkedlist;
/**
* One way linked list data structure
*
* @author 01
* @date 2018-11-08
**/
public class LinkedList<E> {
/**
* Nodes in the list
*/
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();
}
}
/**
* Virtual header node
*/
private Node dummyHead;
/**
* The number of elements in the linked list
*/
private int size;
public LinkedList() {
this.dummyHead = new Node(null, null);
this.size = 0;
}
/**
* Get the number of elements in the list
*
* @return Element number
*/
public int getSize() {
return size;
}
/**
* Is the list empty
*
* @return Empty return true, Otherwise return to false
*/
public boolean isEmpty() {
return size == 0;
}
/**
* In the list of index(0-based) Add new elements to the location e
*
* @param index Where elements are added
* @param e New elements
*/
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed. Illegal index.");
}
Node prev = dummyHead;
// Move prev To index The location of the previous node
for (int i = 0; i < index; i++) {
prev = prev.next;
}
Node node = new Node(e);
node.next = prev.next;
prev.next = node;
// Again , The above three sentences can be completed in one sentence
// prev.next = new Node(e, prev.next);
size++;
}
/**
* Add new elements to the head of the list e
*
* @param e New elements
*/
public void addFirst(E e) {
add(0, e);
}
/**
* Find whether the linked list contains elements e
*/
public boolean contains(E e) {
Node cur = dummyHead.next;
// The first way to traverse a linked list
while (cur != null) {
if (cur.e.equals(e)) {
return true;
}
cur = cur.next;
}
return false;
}
/**
* Remove elements from the list 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--;
}
}
}

Then, based on the linked list structure, the collection can be easily realized . The code is as follows :

package set;
import linkedlist.LinkedList;
/**
* Set based on linked list
*
* @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) {
// Do not store duplicate elements
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();
}
}

Mapping Foundation

mapping (Map) In data structure, it refers to a kind of key-value Data structure of ,key And value There is a one-to-one relationship , So it's called mapping . It's the same as the concept of mapping in mathematics , There is a one-to-one mapping relationship between domain and value domain , It's the function that describes this mapping :

The word mapping is relatively obscure , We can also compare it to a dictionary , That's why some programming languages call it a dictionary ( Commonly abbreviated as dict) Why . Because a dictionary is a typical mapping relationship , A word corresponds to an interpretation , It's also key-value Structure , adopt key We can quickly find value.

In fact, mapping is everywhere in our daily life , for example , Id card -> people 、 license plate number -> Car and license plate -> Employees, etc . therefore Map It plays an important role in many fields , The most typical is the core idea in the field of big data :Map-Reduce, A typical application is word frequency statistics : word -> frequency .

Like a collection , Mapping is also a relatively high-level data structure , The bottom layer can also be implemented by a variety of different data structures , Common underlying implementations are : Linked list 、 Binary search tree 、 Red black tree and hash table . So we need to define a Map The interface is used as the upper image extraction :

package map;
/**
* Mapping interface
*
* @author 01
* @date 2021-01-18
**/
public interface Map<K, V> {
/**
* Additive elements
*
* @param key key
* @param value value
*/
void add(K key, V value);
/**
* according to key Remove elements
*
* @param key key
* @return The deleted value
*/
V remove(K key);
/**
* according to key Query whether the element exists
*
* @param key key
* @return boolean
*/
boolean contains(K key);
/**
* according to key obtain value
*
* @param key key
* @return value
*/
V get(K key);
/**
* change key Of value
*
* @param key key
* @param value value
*/
void set(K key, V value);
/**
* obtain Map The number of elements in
*
* @return Element number
*/
int getSize();
/**
* Judge Map Is it empty
*
* @return boolean
*/
boolean isEmpty();
}

Mapping implementation based on linked list

Use linked lists to map , It is not different from the ordinary linked list , The only difference is that the nodes in the linked list no longer simply store a single element , Instead, two member variables need to be stored separately key and value. The specific implementation code is as follows :

package map;
/**
* Based on linked list Map
*
* @author 01
* @date 2021-01-18
*/
public class LinkedListMap<K, V> implements Map<K, V> {
/**
* The node structure of the linked list , Key value pairs are stored in the node , Not a single element
*/
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();
}
}
/**
* Virtual header node
*/
private final Node dummyHead;
private int size;
public LinkedListMap() {
dummyHead = new Node();
size = 0;
}
/**
* Based on the incoming key Get the nodes in the linked list
*/
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 non-existent , Insert a new element into the head of the linked list
dummyHead.next = new Node(key, value, dummyHead.next);
size++;
} else {
// otherwise , change 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;
// according to key Find the previous node of the node to be deleted
while (prev.next != null) {
if (prev.next.key.equals(key)) {
break;
}
prev = prev.next;
}
if (prev.next != null) {
// Delete the target node
Node delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
size--;
return delNode.value;
}
return null;
}
}

Mapping implementation based on binary search tree

Last , Let's look at the mapping implementation based on binary search tree . After reading the previous implementation case based on linked list , The content of this section is easy to understand , Because the mapping implementation based on binary search tree is the same , Except that the node structure of the tree is different , The rest of the logic is not much different from ordinary binary search trees . The specific implementation code is as follows :

package map;
/**
* Based on binary search tree implementation Map
*
* @author 01
* @date 2021-01-18
*/
public class TreeMap<K extends Comparable<K>, V> implements Map<K, V> {
/**
* The node structure of binary search tree , Key value pairs are stored in the node , Not a single element
*/
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) {
// Add new elements to the binary search tree (key, value)
root = add(root, key, value);
}
/**
* to node Insert elements for the binary search tree of the root (key, value), Recursive implementation
*
* @return Return to the root of the binary search tree after inserting a new node
*/
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;
}
/**
* Return to node In the binary search tree for the root node ,key The node
*/
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;
}
/**
* Return to node Is the node of the minimum value of the binary search tree of the root
*/
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
return minimum(node.left);
}
/**
* Delete the to node The smallest node in the binary search tree for the root
* Returns the root of the new binary search tree after the node is deleted
*/
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) {
// Remove the key from the binary search tree as key The node of
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 the left subtree of the node to be deleted is empty
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
// If the right subtree of the node to be deleted is empty
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
// When the left and right subtrees of the nodes to be deleted are not empty
// Find the smallest node larger than the node to be deleted , That is, the smallest node of the right subtree of the node to be deleted
Node successor = minimum(node.right);
// Use this node to replace the location of the node to be deleted
successor.right = removeMin(node.right);
successor.left = node.left;
return successor;
}
}
}

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[Blow water in a bowl]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210121234656748k.html

  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课程百度云