知识导航
一.集合
1、集合的特点
◼ 集合的特点
不存放重复的元素
对于集合它的主要用途是常用于去重。
集合我们主要记住它不存放重复元素的特点，根据此特点又细化了出许多具体的功能：
1.✓ 存放新增 IP，统计新增 IP 量
2.✓ 存放词汇，统计词汇量
2、集合的接口设计
对于集合接口我们主要是维护它的遍历方法以及访问器。
除此以外在实现集合各个方法是一定要维护它的不重复性
public interface Set<E> {
int size(); //元素数量
boolean isEmpty(); // 是否为空
void claer(); // 清空集合
boolean contains(E element); // 是否包含element元素
void add(E element); // 添加element元素
void remove(E element); // 删除element元素
void traversal(Visitor<E> visitor); // 通过访问器遍历
public static abstract class Visitor<E>{ // 访问器
boolean stop;
public abstract boolean visit(E element);
}
}
3.链表实现集合（listSet）
package set;
import list.LinkedList;
import list.List;
public class listSet<E>implements Set<E>{
private final List<E> list=new LinkedList<>();
public int size(){
return list.size();
}
public boolean isEmpty(){
return list.isEmpty();
}
public void clear(){
list.clear();
}
public boolean contains(E element){
return list.contains(element);
}
//这里就不能写List.add(element)因为集合不能有重复的元素
//这样写就默认重复的元素可有加进去了
public void add(E element){
if(list.contains(element)){
return;
}
list.add(element);
/**
*int index=list.indexOf(element);
* if(index!=List.ELEMENT_NOT_FOUND){
* list.set(index,element);
* }else {
* list.add(element);
* }
*/
}
public void remove(E element){
if(list.indexOf(element)!=List.ELEMENT_NOT_FOUND) {
list.remove(list.indexOf(element));
}
}
public void traversal(Visitor<E> visitor) {
if(visitor==null)
{
return;
}
int n=list.size();
for (int i = 0; i <n ; i++) {
if(visitor.visit(list.get(i))){
return;
}
}
}
}
4.红黑树实现集合（TreeSet）
用红黑树实现集合有一个局限性，红黑树中的元素必须具有可比较性，所以最好传入一个比较器comparator
package set;
import tree.BinaryTree;
import tree.RBTree;
import java.util.Comparator;
@SuppressWarnings("unchecked")
public class TreeSet<E>implements Set<E> {
private RBTree<E> tree=new RBTree<>();
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) {
//用现有Set理的visitor来控制限定条件
return visitor.visit(element);
}
});
}
}
二. 映射
1.映射的特点
映射（ Map） 在有些编程语言中也叫做字典（dictionary，比如 Python、Objective-C、Swift 等）。
既然是字典的功能,那么必然会有两个值。key和value通过key（线索）来找到value。
2.映射的接口设计
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);
boolean containsValue(v value);
void traversal(Visitor<k, v> visitor);
public static abstract class Visitor<k, v> {
boolean stop;
public abstract boolean visit(k key, v value);
}
}
2.红黑树实现映射
package map;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
//红黑树实现映射
//因为现在是两个泛型，红黑树每个节点都存储这两个数据
//如果还是继承以前的节点是不现实的--->所以这里我们需要自己构建一个红黑树
@SuppressWarnings("unchecked")
public class TreeMap <k,v>implements Map<k,v>{
private static final boolean RED=true;
private static final boolean BLACK=false;
int size;
Node<k,v> root;
Comparator<k> comparator;
//红黑树数据必须具有比较性所以传入构造器
public TreeMap(){this(null);}
public TreeMap( Comparator<k> comparator) {
this.comparator=comparator;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
@Override
public void clear() {
root=null;
size=0;
}
private void checkIsNull(k key){
if(key==null)
{
throw new UnsupportedOperationException("key不合法");
}
}
@Override
public v put(k key, v value) {
checkIsNull(key);
// 添加第一个节点
if (root == null) {
//一开始的写法是new Node<>(element,null);对应值和父节点
root = createNode(key,value, null);
size++;
// 新添加节点之后的处理（巧妙之处---写在父类的add中追加判断调整）
//如果主函数创建的是单纯的二叉搜索树则方法体是空不做处理，如果是AvL是则
//遵循重写规则进行恢复
afterPut(root);
//这里的返回是返回它之前的节点，根节点之前没有节点
return null;
}
// 添加的不是第一个节点
// 找到父节点
Node<k,v> parent = root;
Node<k,v> node = root;
int cmp = 0;
do {
cmp = compare(key ,node.key);
parent = node;
if (cmp > 0) {
node = node.right;
} else if (cmp < 0) {
node = node.left;
} else { // 相等，这里注意如果要是相等key,value都赋值给这个节点，返回老value
//相等就覆盖
node.key = key;
v oldValue=node.value;//node被覆盖之前的的value;
node.value=value;
return oldValue;
}
} while (node != null);
// 看看插入到父节点的哪个位置
//到这里就是已经红黑树之前没有这个数据，这完全是新添加的节点，而且添加的位置就是node的位置
Node<k,v> newNode = createNode(key,value, parent);
if (cmp > 0) {
parent.right = newNode;
} else {
parent.left = newNode;
}
size++;
// 新添加节点之后的处理
afterPut(newNode);
return null;
}
private Node<k,v> createNode(k key,v value,Node<k,v> parent){
return new Node<>(key,value,parent);
}
private void afterPut(Node<k,v> node)
{
Node<k,v> parent=node.parent;
//这个代码块包括两种情况--->（1）第一次添加节点（2）叔父节点是红色的情况下，上溢到了根节点
if(parent==null){
black(node);
root=node;
return;
}
if(isBlack(parent))
{
//排除本身就满足条件的哪四种情况,不需要额外处理
return;
}
Node<k,v> uncle=parent.sibling();
Node<k,v> grand=parent.parent;
//叔父节点是红色-->发生上溢
if(isRed(uncle)){
//上溢分裂的情况
black(parent);
black(uncle);
//把祖父节点当成一个新添加的节点加到上面-->解决上溢
afterPut(red(grand));
return;
}
//叔父节点不是红节点
if(parent.isLeftChild())
{
//由于染色顺序并不影响所以可以把统一的染色顺序放在前面red(grand)
//LL RR 单旋
if(node.isLeftChild()){//LL
black(parent);
red(grand);
}else {//LR
black(node);
red(grand);
rotateLeft(parent);
}
rotateRight(grand);
}else{
if(node.isRightChild())//RR
{
black(parent);
red(grand);
}else{//RL
black(node);
red(grand);
rotateRight(parent);
}
rotateLeft(grand);
}
}
private int compare(k e1,k e2){
if (comparator != null) {
return comparator.compare(e1, e2);
}
return ((Comparable<k>)e1).compareTo(e2);
}
private void rotateLeft(Node<k,v> grand) {
Node<k,v> parent = grand.right;
Node<k,v> child = parent.left;
grand.right = child;
parent.left = grand;
afterRotate(grand, parent, child);
}
private void rotateRight(Node<k,v> grand) {
Node<k,v> parent = grand.left;
Node<k,v> child = parent.right;
grand.left = child;
parent.right = grand;
afterRotate(grand, parent, child);
}
protected void afterRotate(Node<k,v> grand, Node<k,v> parent, Node<k,v> child) {
// 让parent称为子树的根节点
parent.parent = grand.parent;
if (grand.isLeftChild()) {
grand.parent.left = parent;
} else if (grand.isRightChild()) {
grand.parent.right = parent;
} else { // grand是root节点
root = parent;
}
// 更新child的parent
if (child != null) {
child.parent = grand;
}
// 更新grand的parent
grand.parent = parent;
}
private Node<k,v> color(Node<k,v> node,boolean color){
//代码习惯：染色的同时返回被染色的节点便于对其进行一些操作
if(node==null)
{
return null;
}
node.color=color;
return node;
}
public Node<k,v> red(Node<k,v> node)
{
return color(node,RED);
}
public Node<k,v> black(Node<k,v> node)
{
return color(node,BLACK);
}
//判断颜色
private boolean iscolor(Node<k,v> node)
{
return node==null?BLACK:node.color;
}
public boolean isRed(Node<k,v> node)
{
return iscolor(node)==RED;
}
public boolean isBlack(Node<k,v> node){
return iscolor(node)==BLACK;
}
@Override
public v get(k key) {
Node<k,v> node=node(key);
return node!=null?node.value:null;
}
//给定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 old=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的节点
replacement.parent=node.parent;
if(node.parent==null){//node是度为一的根节点
root=replacement;
}else if(node==node.parent.left){
node.parent.left=replacement;
}else{
node.parent.right=replacement;
}
afterRemove(node,replacement);
//除了这个if代码块就都是叶子节点了
} else if (node.parent == null) { // node是叶子节点并且是根节点
root=null;
afterRemove(node, null);
} else { // node是叶子节点，但不是根节点
if (node == node.parent.left) {
node.parent.left=null;
} else { // node == node.parent.right
node.parent.right=null;
}
//细节：这里不管删除操作如何进行--都没由对node，parent进行销毁,parent仍然存在
// 删除节点之后的处理
afterRemove(node, null);
}
return old;
}
private Node<k,v> node(k element) {
Node<k,v> node = root;
while (node != null) {
int cmp = compare(element, node.key);
if (cmp == 0) return node;
if (cmp > 0) {
node = node.right;
} else { // cmp < 0
node = node.left;
}
}
return null;
}
private void afterRemove(Node<k,v> node,Node<k,v> replacement){
//b树类比红黑树一定是删除的最后一层。如果要删除的是红色，由于黑色是主体，
// 所以要删除的节点一定度为0的红色叶子节点，不会影响原本红黑树的规则，所以不用调整，直接结束函数
if(isRed(node)){
return;
}
/**
* 一定要清楚afterRemove的作用是删除之后的调整，不是主体删除方法。
* 作用：对于不符合红黑树性质的操作及时进行调整
*
* 问：对于删除度为2的黑色节点，是不是可是囊括
* 答：可以：因为删除度为2的黑色节点，找到前驱后，还是删除红色节点不用处理，染黑替代节点并不影响，因为已经删除
*
* 为什么黑色节点的替代不能为黑色节点
* 因为b树的删除都是在最后一层进行操作，如果黑色节点子节点依然是一个黑色节点，由于黑色才是主体
* 不会融入到一个节点中，所以只会向下增高一层，不符合删除在最后一层操作。，
*/
if(isRed(replacement)){
//染黑：避免出现连续两个红色节点
black(replacement);
return;
}
/**
* 处理最后一种情况-->删除度为0的黑色叶子节点的调整方法
*
* 删除度为0的黑色叶子节点的调整方法肯定会造成下溢
* 补救:(1)看看兄弟节点能不能借
* a:兄弟节点能借的条件：1.兄弟节点是黑色 2.兄弟节点至少拥有一个红色子节点
* ----------------------------------------
* 能借后做出的操作：
* 进行旋转操作
* 旋转之后的中心节点继承 parent 的颜色
* 旋转之后的左右节点染为 BLACK（因为此时红色子节点已经旋上去了）
*
* 旋转有三种情况：LL LR LL
*
* 🤩🤩特殊情况1：
* 如果被删除的是黑色，它的父节点也是黑色，删除后黑色父节点也会向下合并，造成父节点继续下溢
*只需将这个父节点当成一个新的被删除的黑色节点递归调用afterRemove方法，重复利用代码
*
* 🤩🤩特殊情况2：
* 🚩🚩🚩如果兄弟节点是红色，对于b树的性质，【黑色节点与其红色节点组成一个b树节点】
* 可知：红色节点一定在父节点中-->红色的节点的子节点一定是黑的，可以借侄子的【想办法将侄子变成兄弟】
* 强制将侄子变成兄弟再次套用兄弟节点是黑色是的代码
*-----------------------------------------------
*/
Node<k,v> parent=node.parent;
if(parent==null)
{
return;
}
//这么写有问题：node已经被删除--->指向node的线已经断了
//Node<k,v> sibling =node.sibling();
/**
* 需要间接求出兄弟节点
* 只需知道被删除的节点先前是在parent的左边还是右边，进而知道sibling是parent.left还是parent.right
*/
/**
* 为什么以此作为判定标准：
* 因为在二叉搜索树的删除中，删除黑色叶子节点,已经将一边置为null
* if (node == node.parent.left) {
* node.parent.left=null;
* } else { // node == node.parent.right
* node.parent.right=null;
* }
*/
//有特殊情况
boolean left=parent.left==null||node.isLeftChild();
Node<k,v> sibling=left?parent.right:parent.left;
if(left){//node是在左子树，兄弟节点在右边
if(isRed(sibling)){
black(parent);
red(sibling);
rotateLeft(parent);
//更新兄弟
sibling=parent.right;
}
//兄弟节点是黑色-->判断是否有红色子节点
//没有一个红色子节点--->父节点向下合并
/**
* 为什么以父节点是不是黑的为判定条件
* 因为如果父节点是红色，那它肯定不是主体，向下合并后，parent本身并没有下溢
* 如果父节点是黑色，那他向下合并后，自身也会下溢
*
*/
if(isBlack(sibling.left)&&isBlack(sibling.right)){
boolean parentBlack=isBlack(parent);
black(parent);
red(sibling);
//这种情况父节点向下合并，父节点的位置也会下溢
if(parentBlack){
//三黑局面没有替代节点
afterRemove(parent,null);
}
}else {//至少有一个红色子节点
//判断是LL LR.....
//三种情况:LL LR (LL或LR)
//可以先统一进行左旋转然后在统一进行右旋转
//如何区分LR左子节点是黑的
if(isBlack(sibling.left)) {//LR情况
rotateLeft(sibling);
//左旋转后兄弟节点已经发生了变化
sibling = parent.left;
}
//LL 情况
//现在的sibling已经更新过是图中的78
color(sibling,iscolor(parent));
black(parent);
black(sibling.left);
rotateRight(parent);
}
}else {//node是在右子树，兄弟节点在左边
//🤩🤩特殊情况2：
if(isRed(sibling)){
black(parent);
red(sibling);
rotateRight(parent);
//更新兄弟
sibling=parent.left;
}
//兄弟节点是黑色-->判断是否有红色子节点
//没有一个红色子节点--->父节点向下合并
/**
* 为什么以父节点是不是黑的为判定条件
* 因为如果父节点是红色，那它肯定不是主体，向下合并后，parent本身并没有下溢
* 如果父节点是黑色，那他向下合并后，自身也会下溢
*
*/
if(isBlack(sibling.left)&&isBlack(sibling.right)){
boolean parentBlack=isBlack(parent);
black(parent);
red(sibling);
//这种情况父节点向下合并，父节点的位置也会下溢
if(parentBlack){
//三黑局面没有替代节点
afterRemove(parent,null);
}
}else {//至少有一个红色子节点
//判断是LL LR.....
//三种情况:LL LR (LL或LR)
//可以先统一进行左旋转然后在统一进行右旋转
//如何区分LR左子节点是黑的
if(isBlack(sibling.left)) {//LR情况
rotateLeft(sibling);
//左旋转后兄弟节点已经发生了变化
sibling = parent.left;
}
//LL 情况
//现在的sibling已经更新过是图中的78
color(sibling,iscolor(parent));
black(parent);
black(sibling.left);
rotateRight(parent);
}
}
}
protected Node<k,v> predecessor(Node<k,v> node) {
if (node == null) return null;
// 前驱节点在左子树当中（left.right.right.right....）
Node<k,v> p = node.left;
if (p != null) {
while (p.right != null) {
p = p.right;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.left) {
node = node.parent;
}
// node.parent == null
// node == node.parent.right
return node.parent;
}
protected Node<k,v> successor(Node<k,v> node) {
if (node == null) return null;
// 前驱节点在左子树当中（right.left.left.left....）
Node<k,v> p = node.right;
if (p != null) {
while (p.left != null) {
p = p.left;
}
return p;
}
// 从父节点、祖父节点中寻找前驱节点
while (node.parent != null && node == node.parent.right) {
node = node.parent;
}
return node.parent;
}
@Override
public boolean containsKey(k key) {
return node(key)!=null;
}
private boolean Equals(v v1,v v2){
return v1==null?v2==null:v1.equals(v2);
}
@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();
boolean com=Equals(value,node.value);
if(com)
{
return true;
}
if(node.left!=null)
{
queue.offer(node.left);
}
if(node.right!=null)
{
queue.offer(node.right);
}
}
return false;
}
//前序遍历
@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);
}
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 isLeftChild() {
return parent != null && parent.left ==this;
}
public boolean isRightChild() {
return parent != null && parent.right == this;
}
public boolean hasToChildren() {
return left != null && right != null;
}
public Node<k, v> sibling() {
if (isLeftChild()) {
return right;
}
if (isRightChild()) {
return left;
}
return null;
}
public boolean hasTwoChildren(){
return left!=null&&right!=null;
}
}
}
三.用映射实现集合（HashMap实现HashSet）
上面我们提到，映射有两个关键的存储数据key value.映射由 红黑树来实现，在红黑树中如果添加的是相同元素会实现覆盖操作，所以用红黑树实现的映射默认没有重复元素，所以我们不难看出如果我们把红黑树中的value 去掉不就符合集合的所有要求了吗,所以我们完全可以用映射来实现集合。
package bite;
import map.Map;
import map.TreeMap;
import java.util.Objects;
//用映射实现集合
//映射去掉value正好符合集合的要求
public class TreeSet<E> implements Set<E>{
Map<E, Objects> map=new TreeMap<>();
@Override
public int size() {
return map.size();
}
@Override
public boolean isEmpty() {
return map.isEmpty();
}
@Override
public void clear() {
map.clear();
}
@Override
public boolean contains(E element) {
return map.containsKey(element);
}
@Override
public void add(E element) {
map.put(element,null);
}
@Override
public void remove(E element) {
map.remove(element);
}
@Override
public void traversal(Visitor<E> visitor) {
map.traversal(new Map.Visitor<E, Objects>() {
@Override
public boolean visit(E key, Objects value) {
visitor.visit(key);
return false;
}
});
}
}
