前言
在上一篇中咱们基于数组和链表实现了Map的相干操作，然而对于数据量稍大的状况下，这两种实现形式效率都比拟低，为了改良这个问题，本篇咱们未来学习二叉树，并通过二叉树来实现上一篇中定义的Map构造
二叉树简介
尽管大家都晓得二叉树是什么，然而为了保障文章的完整性，这里还是简略说说什么是二叉树
二叉树中每个节点都蕴含了两个指针指向本人的左子树和右子树。
二叉树的每个节点都蕴含了一个Key, 并且每个节点的Key都大于其左子树中的任意节点，小于右子树中的任意节点。
节点的数据结构定义：
class Node { private K key; private V value; private Node left; private Node right; private int size = 1; public Node(K key, V value) { this.key = key; this.value = value; }}复制代码size 记录以后节点所在子树的节点个数，计算形式：size=左子树的个数 + 1 + 右子树的个数
基于二叉树实现Map
在上一篇《基于数组或链表实现Map》中咱们定义了Map的接口，本篇咱们持续应用该map接口
public interface Map<K, V> { void put(K key, V value); V get(K key); void delete(K key); int size(); Iterable<K> keys(); Iterable<TreeNode> nodes(); default boolean contains(K key) { return get(key) != null; } default boolean isEmpty() { return size() == 0; }}public interface SortedMap<K extends Comparable<K>, V> extends Map<K, V> { int rank(K key); void deleteMin(); void deleteMax(); K min(); K max();}复制代码查问
在二叉树中查找一个键最简略间接的形式就是应用递归，把查找的key和节点的key进行比拟，如果较小就去左子树中持续递归查找，如果较大就在右子树中查找，如果相等，示意已找到间接返回value，如果递归完结还未找到就返回null
代码实现：
@Overridepublic V get(K key) { if (Objects.isNull(key)) { throw new IllegalArgumentException("key can not null"); } Node node = get(root, key); return Objects.isNull(node) ? null : node.value;}private Node get(Node node, K key) { if (Objects.isNull(node)) { return null; } int compare = key.compareTo(node.key); if (compare > 0) { return get(node.right, key); } else if (compare < 0) { return get(node.left, key); } else { return node; }}复制代码查问出最大值和最小值
在二叉树中咱们可能会常常应用到查问树中的最大值和最小值，包含前面咱们的删除操作也会应用到，所以这里咱们须要实现这两个办法；
最大值的实现： 从根节点开始沿着右子树递归，直到遇到右子树为null的时候就完结，此时的节点就是最大值 最小值的实现： 从根节点开始沿着左子树递归，晓得遇到左子树为null的时候就完结，此时的节点就是最小值
@Overridepublic K max() { Node max = max(root); return max.key;}protected Node min(Node node) { if (Objects.isNull(node.left)) { return node; } return min(node.left);}protected Node max(Node node) { if (Objects.isNull(node.right)) { return node; } return max(node.right);}复制代码插入
从下面的实现咱们能够看出二叉树的查询方法和上篇中数组二分查找法实现的一样简略高效，这是二叉树的一个重要个性，而且二叉树的插入与查问操作一样简略，现实状况下插入和查问操作工夫复杂度都是log(N)
插入操作的实现思路： 与查问操作相似，仍然是递归，如果put的key值比以后节点大就须要去右子树递归，如果较小就去左子树递归，如果相等就间接更新节点的值。如果递归完结后还未找到值就新建一个节点并返回
private Node put(Node node, K key, V value) { if (Objects.isNull(node)) { return new Node(key, value); } int compare = key.compareTo(node.key); if (compare > 0) { node.right = put(node.right, key, value); } else if (compare < 0) { node.left = put(node.left, key, value); } else { node.value = value; } node.size = size(node.left) + 1 + size(node.right); return node;}private int size(Node node) { if (Objects.isNull(node)) { return 0; } return node.size;}复制代码其中size的计算在后面曾经说到，以后节点的size = 左子树.size + 1 + 右子树.size
删除最大值和最小值
二叉树中绝对比拟麻烦的操作就是删除操作，所以咱们先来理解下删除最大值和最小值应该如何实现。
删除最小值：和后面实现查找最小值有些类似，沿着右边门路始终深刻，直到遇到一个节点的左子树为null, 那么这个以后节点就是最小值，在递归中把以后节点的右子树返回即可；
最大值实现思路相似
代码如下：
@Overridepublic void deleteMin() { root = deleteMin(root);}public Node deleteMin(Node node) { if (Objects.isNull(node.left)) { return node.right; } node.left = deleteMin(node.left); node.size = size(node.left) + 1 + size(node.right); return node;}@Overridepublic void deleteMax() { root = deleteMax(root);}public Node deleteMax(Node node) { if (Objects.isNull(node.right)) { return node.left; } node.right = deleteMax(node.right); node.size = size(node.left) + 1 + size(node.right); return node;}复制代码删除
咱们能够通过相似的形式去删除只有一个子节点或者是没有子节点的节点；然而如果遇到须要删除有两个节点的节点应该怎么操作呢？
两种思路：用左子树的最大值替换待删除节点，而后删除掉左子树的最大值；或者是用右子树中的最小值替换待删除节点，而后删除右子树中的最小值
步骤：
- 从该节点的左子树中取出最大值或者是从右子树中取出最小值
- 用最大值或者最小值替换以后的节点
- 调用删除最大值或者删除最小值
代码实现
@Overridepublic void delete(K key) { root = delete(root, key);}private Node delete(Node node, K key) { if (Objects.isNull(node)) { return null; } int compare = key.compareTo(node.key); if (compare > 0) { node.right = delete(node.right, key); } else if (compare < 0) { node.left = delete(node.left, key); } else { if (Objects.isNull(node.left)) { return node.right; } if (Objects.isNull(node.right)) { return node.left; } Node max = max(node.left); node.key = max.key; node.value = max.value; node.left = deleteMax(node.left); } node.size = size(node.left) + 1 + size(node.right); return node;}复制代码剖析
应用二叉树实现的Map运行的效率取决于树的形态，而树的形态取决于数据输出的程序；最好的状况下二叉树是均衡的，那么get、put的工夫复杂度都是log(N); 然而如果插入的数据是有序的，那么二叉树就调演变成链表，那么get、put的性能将会大大减低；
基于这个问题，咱们会持续改良咱们实现的Map，下一篇咱们将会学习应用红黑树来实现咱们的Map操作，无论数据插入的程序如何都能保障二叉树近似均衡
参考：《2020最新Java根底精讲视频教程和学习路线！》
链接：https://juejin.cn/post/694227...