DS-Map

目录

接口定义使用链表实现

底层链表定义linkedMap 使用二分搜索树实现

底层二分搜索树定义BSMap 接口定义

public interface SelfMap { boolean isEmpty(); int getSize(); boolean containsKey(K k); void add(K k, V v); void remove(K k); void set(K k, V v); V get(K k); void show();}

使用链表实现 底层链表定义

将原来的Mylink改成双列存储就行

public class Mylink { private class Node { private K key; // key private V val; // value private Node next; // 指向下个结点的引用 Node(K key, V val) { this.key = key; this.val = val; this.next = null; } @Override public String toString() { return "(" + key + "," + val + ")"; } } private Node head; // 头结点 private int size; // 链表中结点的个数 public Mylink() { head = null; } public boolean isEmpty() { return this.size == 0; } public int getSize() { return this.size; } public boolean contains(K key) { Node curNode = head; while (curNode != null && !curNode.key.equals(key)) { curNode = curNode.next; } return curNode != null; } public void add(K key, V val) { boolean result = contains(key); if (result) { update(key, val); } else { Node node = new Node(key, val); node.next = head; head = node; // 更新size this.size++; } } public void remove(K key) { Node dummyHead = new Node(null, null); dummyHead.next = head; Node preNode = dummyHead; while (preNode.next != null) { if (preNode.next.key.equals(key)) { Node delNode = preNode.next; preNode.next = delNode.next; delNode.next = null; this.size--; } else { preNode = preNode.next; } } this.head=dummyHead.next; } public void removeDg(K key) { head = removeDg(head, key); } private Node removeDg(Node node, K key) { // 递归到底的情况 if (node == null) { return null; } // 递归操作 Node newNode = removeDg(node.next, key); if (node.key.equals(key)) { this.size--; return newNode; } else { node.next = newNode; return node; } } public void update(K key, V val) { Node curNode = head; while (curNode != null) { if (curNode.key.equals(key)) { curNode.val = val; return; } curNode = curNode.next; } throw new IllegalArgumentException("指定的key不存在"); } public V get(K key) { Node curNode = head; while (curNode != null) { if (curNode.key.equals(key)) { return curNode.val; } curNode = curNode.next; } return null; } public void show() { Node cur = head; while (cur != null) { System.out.println(cur); cur = cur.next; } } @Override public String toString() { StringBuilder sb = new StringBuilder(); Node cur = head; while (cur != null) { sb.append(cur + "-->"); cur = cur.next; } return sb.toString(); }}

linkedMap

public class linkedMap implements SelfMap { Mylink data; public linkedMap() { this.data = new Mylink<>(); } @Override public boolean isEmpty() { return data.isEmpty(); } @Override public int getSize() { return data.getSize(); } @Override public boolean containsKey(K k) { return data.contains(k); } @Override public void add(K k, V v) { data.add(k, v); } @Override public void remove(K k) { data.remove(k); } public void removeDg(K k) { data.removeDg(k); } @Override public void set(K k, V v) { data.update(k, v); } @Override public V get(K k) { return data.get(k); } @Override public void show() { data.show(); }}

使用二分搜索树实现 底层二分搜索树定义

public class BinarySearch, V> { class Node { K key; V val; Node left; Node right; public Node(K key, V val) { this.val = val; this.key = key; this.left = this.right = null; } @Override public String toString() { return "(" + key + "," + val + ")"; } } private Node root; int size; public BinarySearch() { this.root = null; this.size = 0; } public boolean isEmpty() { return this.root == null; } public void add(K key, V val) { if (contains(key) != null) { set(key, val); return; } // 使用递归的方式添加结点 root = add(root, key, val); this.size += 1; } private Node add(Node node, K key, V val) { // 递归到底的情况 if (node == null) { Node newNode = new Node(key, val); return newNode; } // 递归操作 if (key.compareTo(node.key) > 0) { node.right = add(node.right, key, val); } else { node.left = add(node.left, key, val); } return node; } public Node contains(K key) { return contains(root, key); } private Node contains(Node node, K key) { // 递归到底的情况 if (node == null) { return null; } // 递归操作 if (node.key.compareTo(key) == 0) { return node; } else if (key.compareTo(node.key) > 0) { return contains(node.right, key); } else { return contains(node.left, key); } } public List middleOrder() { List result = new ArrayList<>(); middleOrder(root, result); return result; } private void middleOrder(Node node, List result) { // 递归到底的情况 if (node == null) { return; } // 先遍历左树，在获取中间值，然后遍历右树 middleOrder(node.left, result); result.add(node.toString()); middleOrder(node.right, result); } public Node findMixNodeDG() { if (root == null) { return null; } return findMixNodeDG(root); } private Node findMixNodeDG(Node root) { // 递归到底的情况 if (root.left == null) { return root; } // 递归操作 return findMixNodeDG(root.left); } private void removeMixNode() { //先找到最小结点 Node mixNodeval = findMixNodeDG(); if (mixNodeval == null) { System.out.println("the tree is empty"); return; } System.out.println("Find mixNode value is " + mixNodeval); // 进行删除操作 root = removeMixNode(root); this.size -= 1; } private Node removeMixNode(Node node) { if (node.left == null) { // 进行删除操作 Node rightNode = node.right; node.right = null; return rightNode; } node.left = removeMixNode(node.left); return node; } public V removeNode(K key) { if (root == null) { System.out.println("The tree is null"); return null; } // 查找结点 Node node = findNodeDG(root, key); if (node != null) { //删除操作 root = removeNode(root, key); this.size -= 1; return node.val; } return null; } private Node removeNode(Node node, K key) { // 递归到底的情况，找到了删除的结点 if (node.key.compareTo(key) == 0) { if (node.left == null) { Node rightNode = node.right; node.right = null; return rightNode; } else if (node.right == null) { Node leftNode = node.left; node.left = null; return leftNode; } else { // 左右都不为空 // 1、找node的后继（node.right中的最小结点） Node s = findMixNodeDG(node.right); // 2、从node.right中删除最小结点 Node rightRoot = removeMixNode(node.right); // 3、使用后继结点替换node s.left = node.left; s.right = rightRoot; // 4、生成新树，新树的根节点就是后继结点，返回新树的根结点 node.left = node.right = null; return s; } } // 递归操作 if (node.key.compareTo(key) > 0) { node.left = removeNode(node.left, key); } else { node.right = removeNode(node.right, key); } return node; } private Node findNodeDG(Node node, K key) { // 找到最终还没有找到，就返回null if (node == null) { return null; } if (node.key.compareTo(key) == 0) { return node; } else if (node.key.compareTo(key) > 0) { return findNodeDG(node.left, key); } else { return findNodeDG(node.right, key); } } public V get(K key) { return get(root, key); } private V get(Node node, K key) { if (node == null) { return null; } if (node.key.compareTo(key) == 0) { return node.val; } else if (node.key.compareTo(key) > 0) { return get(node.left, key); } else { return get(node.right, key); } } public void set(K k, V v) { Node node = contains(k); if (node == null) { return; } // 进行更新操作 set(root, k, v); } private void set(Node node, K k, V v) { if (node.key.compareTo(k) == 0) { node.val = v; return; } else if (node.key.compareTo(k) > 0) { set(node.left, k, v); } else { set(node.right, k, v); } } public int getSize() { return this.size; } public void show() { List list = this.middleOrder(); list.forEach(System.out::println); }}

BSMap

增删改查效率为树的高度O(logn)

public class BSMap, V> implements SelfMap { BinarySearch data; public BSMap() { this.data = new BinarySearch<>(); } @Override public boolean isEmpty() { return data.isEmpty(); } @Override public int getSize() { return data.getSize(); } @Override public boolean containsKey(K k) { return data.contains(k) != null; } @Override public void add(K k, V v) { data.add(k, v); } @Override public void remove(K k) { data.removeNode(k); } @Override public void set(K k, V v) { data.set(k, v); } @Override public V get(K k) { return data.get(k); } @Override public void show() { data.show(); }}