乐趣区

关于java:基于二叉树实现Map

jiezi

前言

在上一篇中咱们基于数组和链表实现了 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

代码实现：

@Override
public 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 的时候就完结，此时的节点就是最小值 

@Override
public 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, 那么这个以后节点就是最小值，在递归中把以后节点的右子树返回即可；

最大值实现思路相似

代码如下：

@Override
public 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;
}

@Override
public 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;
}
复制代码

删除

咱们能够通过相似的形式去删除只有一个子节点或者是没有子节点的节点；然而如果遇到须要删除有两个节点的节点应该怎么操作呢？

两种思路：用左子树的最大值替换待删除节点，而后删除掉左子树的最大值；或者是用右子树中的最小值替换待删除节点，而后删除右子树中的最小值

步骤：

  1. 从该节点的左子树中取出最大值或者是从右子树中取出最小值
  2. 用最大值或者最小值替换以后的节点
  3. 调用删除最大值或者删除最小值

代码实现 

@Override
public 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…

退出移动版