数据结构篇 11、映射 Map 及其三种底层实现，android 插件化框架

public class BSTMap<K extends Comparable<K>, V> implements Map<K, V> {

private class Node{public K key;public V value;public Node left

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》
浏览器打开：qq.cn.hn/FTe 免费领取

, right;

public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;}}

private Node root;private int size;

public BSTMap(){root = null;size = 0;}

@Overridepublic int getSize(){return size;}

@Overridepublic boolean isEmpty(){return size == 0;}

// 向二分搜索树中添加新的元素(key, value)@Overridepublic void add(K key, V value){root = add(root, key, value);}

// 向以 node 为根的二分搜索树中插入元素(key, value)，递归算法// 返回插入新节点后二分搜索树的根 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 // key.compareTo(node.key) == 0node.value = value;

return node;}

// 返回以 node 为根节点的二分搜索树中，key 所在的节点 private Node getNode(Node node, K key){

if(node == null)return null;

if(key.compareTo(node.key) == 0)return node;else if(key.compareTo(node.key) < 0)return getNode(node.left, key);else // if(key.compareTo(node.key) > 0return getNode(node.right, key);}

@Overridepublic boolean contains(K key){return getNode(root, key) != null;}

@Overridepublic V get(K key){Node node = getNode(root, key);return node == null ? null : node.value;}

@Overridepublic 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;}

// 从二分搜索树中删除键为 key 的节点 @Overridepublic V remove(K key){

Node node = getNode(root, key);if(node != null){root = remove(root, key);return node.value;}

return null;}

// 删除掉以 node 为根的二分搜索树中键为 key 的节点, 递归算法// 返回删除节点后新的二分搜索树的根 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{ // key.compareTo(node.key) == 0

// 待删除节点左子树为空的情况 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;

node.left = node.right = null;

return successor;}}}

4、AVL 树实现的映射 Map

AVL 树实现的映射 Map 如下所示，我们在实现 AVL 树时就定义了两个泛型，所以我们在使用 AVL 树实现映射 Map 时不需要重新实现 AVL 树了，因此我们实现的映射 Map 就是对 AVL 树 api 的一层封装；对 AVL 树不了解的可以看数据结构篇 07；

public class AVLMap<K extends Comparable<K>, V> implements Map<K, V> {

private AVLTree<K, V> avl;

public AVLMap(){avl = new AVLTree<>();}

@Overridepublic int getSize(){return avl.getSize();}

@Overridepublic boolean isEmpty(){return avl.isEmpty();}

@Overridepublic void add(K key, V value){avl.add(key, value);}

@Overridepublic boolean contains(K key){return avl.contains(key);}@Overridepublic V get(K key){return avl.get(key);}@Overridepublic void set(K key, V newValue){avl.set(key, newValue);}@Overridepublic V remove(K key){return avl.remove(key);}}