## 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.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
*
*/
public boolean isEmpty() {
return size == 0;
}
/**
* Add a new element to the binary search tree e
*
* @param e The new element
*/
if (root == null) {
// The root node is empty
root = new Node(e);
size++;
} else {
}
}
/**
* 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
} else {
// Elements e Greater than node Element of node , Go to the right tree
}
}
/**
* 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> {
/**
*
* @param 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
}
@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
**/
/**
* 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();
}
}
/**
*/
/**
* The number of elements in the linked list
*/
private int size;
this.size = 0;
}
/**
* Get the number of elements in the list
*
* @return Element number
*/
public int getSize() {
return size;
}
/**
* Is the list empty
*
*/
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.");
}
// 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++;
}
/**
*
* @param e New elements
*/
}
/**
* Find whether the linked list contains elements e
*/
public boolean contains(E e) {
// 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) {
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;
/**
* Set based on linked list
*
* @author 01
* @date 2021-01-18
**/
public class LinkedListSet<E> implements Set<E> {
}
@Override
// Do not store duplicate elements
}
}
@Override
public void remove(E e) {
}
@Override
public boolean contains(E e) {
}
@Override
public int getSize() {
}
@Override
public boolean 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> {
/**
*
* @param key key
* @param value 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();
}
}
/**
*/
private int size;
size = 0;
}
/**
* Based on the incoming key Get the nodes in the linked list
*/
private Node getNode(K key) {
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
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) {
// 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)
}
/**
* 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) {
} else if (key.compareTo(node.key) > 0) {
} 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 .

https://javamana.com/2021/01/20210121234656748k.html