基于二分搜索树的集合实现
集合（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是有具有一对一关系的，所以称之为映射。这与数学中的映射概念一样，定义域与值域具有一对一的映射关系，描述这个映射关系的是函数：
image.png
映射这个词相对来说有些晦涩，我们也可以将其类比成字典，这也是为什么一些编程语言中将其称为字典（通常缩写为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;
}
}
}
网友评论