数据结构与算法（第一季）：集合与映射
2022-01-05 本文已影响0人
萧1帅
一、集合（Set）
- 不存放重复的元素
- 常用于去重
- 存放新增IP，统计新增IP量
- 存放词汇，统计词汇量
- 集合的内部实现能使用哪些数据结构？
- 动态数组
- 链表
- 二叉搜索树（AVL树，红黑树）
二、集合的接口设计
public interface Set<E> {
int size();
boolean isEmpty();
void clear();
boolean contains(E element);
void add(E element);
void remove(E element);
void traversal(Visitor<E> visitor); //遍历集合
public static abstract class Visitor<E> {
boolean stop;
public abstract boolean visit(E element);
}
}
复制代码
三、集合的实现
1、通过链表实现集合
- 复杂度为O(n)
public class ListSet<E> implements Set<E> {
private List<E> list = new LinkedList<>();
@Override
public int size() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
@Override
public void clear() {
list.clear();
}
@Override
public boolean contains(E element) {
return list.contains(element);
}
@Override
public void add(E element) {
int index = list.indexOf(element); // 获取该元素的索引
if (index != List.ELEMENT_NOT_FOUND) { // 存在就覆盖
list.set(index, element);
} else { // 不存在就添加
list.add(element);
}
}
@Override
public void remove(E element) {
int index = list.indexOf(element);
if (index != List.ELEMENT_NOT_FOUND) {
list.remove(index);
}
}
@Override
public void traversal(Visitor<E> visitor) {
if (visitor == null) return;
int size = list.size();
for (int i = 0; i < size; i++) {
if (visitor.visit(list.get(i))) return;
}
}
}
复制代码
2、通过红黑树实现集合
- 复杂度为O(logn)
- 元素必须具备可比较性，否则只能使用哈希表
public class TreeSet<E> implements Set<E> {
private RBTree<E> tree;
public TreeSet() {
this(null);
}
public TreeSet(Comparator<E> comparator) {
tree = new RBTree<>(comparator);
}
@Override
public int size() {
return tree.size();
}
@Override
public boolean isEmpty() {
return tree.isEmpty();
}
@Override
public void clear() {
tree.clear();
}
@Override
public boolean contains(E element) {
return tree.contains(element);
}
@Override
public void add(E element) {
tree.add(element);// 红黑树默认具有去重功能，直接添加即可。
}
@Override
public void remove(E element) {
tree.remove(element);
}
@Override
public void traversal(Visitor<E> visitor) {
tree.inorder(new BinaryTree.Visitor<E>() {
@Override
public boolean visit(E element) {
return visitor.visit(element);
}
});
}
}
复制代码
四、映射（Map）
- Map在有些编程语言中也叫做字典（dictionary）
- Map的每一个key是唯一的
image
- 类似
Set，Map可以直接利用之前学习的链表，二叉搜索树（AVL树，红黑树）等数据结构来实现。 - 添加，删除，搜索的时间复杂度是
O(logn) - 特点
-
Key必须具备可比较性。 - 元素的分布是有顺序的（
key大的在右边，小的在左边）。
-
- 在实际应用中：
-
map中的存储的元素不需要讲究顺序。 -
map中的key不需要具备可比较性。 - 不考虑顺序和
key的可比较性，map有更优的实现方案，平均时间复杂度可达到O(1)，那就是采取哈希表来实现map。
-
五、映射的接口设计
- 可以在
Map的基础上实现一个TreeMap
public interface Map<K, V> {
int size();
boolean isEmpty();
void clear();
V put(K key, V value); //添加元素
V get(K key);
V remove(K key);
boolean containsKey(K key); //查找key是否存在
boolean containsValue(V value); //查找value是否存在
void traversal(Visitor<K, V> visitor); //元素遍历
public static abstract class Visitor<K, V> {
boolean stop;
public abstract boolean visit(K key, V value);
}
}
复制代码
六、映射的实现（TreeMap）
- 思路是将
映射直接通过红黑树来实现，而不仅仅是通过红黑树存储映射的值。
1、声明节点
private static class Node<K, V> {
K key;
V value;
boolean color = RED;
Node<K, V> left;
Node<K, V> right;
Node<K, V> parent;
public Node(K key, V value, Node<K, V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
public boolean isLeaf() {
return left == null && right == null;
}
public boolean hasTwoChildren() {
return left != null && right != null;
}
public boolean isLeftChild() {
return parent != null && this == parent.left;
}
public boolean isRightChild() {
return parent != null && this == parent.right;
}
public Node<K, V> sibling() {
if (isLeftChild()) {
return parent.right;
}
if (isRightChild()) {
return parent.left;
}
return null;
}
}
复制代码
2、put函数实现
@Override
public V put(K key, V value) {
keyNotNullCheck(key); // key不能为空
// 添加第一个节点
if (root == null) {
root = new Node<>(key, value, null);
size++;
// 新添加节点之后的处理
afterPut(root); //修复红黑树性质
return null;
}
// 添加的不是第一个节点
// 找到父节点
Node<K, V> parent = root;
Node<K, V> node = root;
int cmp = 0;
do {
cmp = compare(key, node.key); //比较传入的key与原节点key
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等
node.key = key; //覆盖key
V oldValue = node.value;
node.value = value; //覆盖value
return oldValue; //返回原节点值
}
} while (node != null);
// 看看插入到父节点的哪个位置
Node<K, V> newNode = new Node<>(key, value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
afterPut(newNode);
return null; //新添加节点，返回空。
}
复制代码
3、get函数实现
- 通过
key先找到node节点，然后再返回节点的值。
@Override
public V get(K key) {
Node<K, V> node = node(key);
return node != null ? node.value : null;
}
private Node<K, V> node(K key) {
Node<K, V> node = root;
while (node != null) {
int cmp = compare(key, node.key);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
复制代码
4、remove函数实现
- 先通过
key找到节点，然后再删除节点。
@Override
public V remove(K key) {
return remove(node(key));
}
private V remove(Node<K, V> node) {
if (node == null) return null;
size--;
V oldValue = node.value;
if (node.hasTwoChildren()) { // 度为2的节点
// 找到后继节点
Node<K, V> s = successor(node);
// 用后继节点的值覆盖度为2的节点的值
node.key = s.key;
node.value = s.value;
// 删除后继节点
node = s;
}
// 删除node节点（node的度必然是1或者0）
Node<K, V> replacement = node.left != null ? node.left : node.right;
if (replacement != null) { // node是度为1的节点
// 更改parent
replacement.parent = node.parent;
// 更改parent的left、right的指向
if (node.parent == null) { // node是度为1的节点并且是根节点
root = replacement;
} else if (node == node.parent.left) {
node.parent.left = replacement;
} else { // node == node.parent.right
node.parent.right = replacement;
}
// 删除节点之后的处理
afterRemove(replacement);
} else if (node.parent == null) { // node是叶子节点并且是根节点
root = null;
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left = null;
} else { // node == node.parent.right
node.parent.right = null;
}
// 删除节点之后的处理
afterRemove(node);
}
return oldValue;
}
复制代码
5、contains函数实现
- 因为
value没有可比较性，所以containsValue只有通过树的遍历来查找value是否存在。
@Override
public boolean containsKey(K key) {
return node(key) != null;
}
@Override
public boolean containsValue(V value) {
if (root == null) return false;
//层序遍历
Queue<Node<K, V>> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node<K, V> node = queue.poll();
if (valEquals(value, node.value)) return true;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
return false;
}
private boolean valEquals(V v1, V v2) {
return v1 == null ? v2 == null : v1.equals(v2);
}
复制代码
6、traversal函数实现
- 中序遍历
@Override
public void traversal(Visitor<K, V> visitor) {
if (visitor == null) return;
traversal(root, visitor);
}
private void traversal(Node<K, V> node, Visitor<K, V> visitor) {
if (node == null || visitor.stop) return;
traversal(node.left, visitor);
if (visitor.stop) return;
visitor.visit(node.key, node.value);
traversal(node.right, visitor);
}
复制代码
