Implement Map based on binary tree

IDEA plug-ins commonly used by programmers: github.com/silently952…

Wechat official account: Beta learning Java

preface

In the previous article, we implemented Map operations based on arrays and linked lists. However, under the circumstance of a slightly large amount of data, these two implementation methods are inefficient. In order to improve this problem, we will learn binary trees in the future and implement the Map structure defined in the previous article through binary trees

Introduction to binary trees

We all know what a binary tree is, but for the sake of completeness, what is a binary tree

Each node in a binary tree contains two Pointers to its left and right subtrees.

Each node of a binary tree contains a Key, and the Key of each node is larger than any node in its left subtree and smaller than any node in its right subtree.

Data structure definition of node:

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; }}Copy the code

Size Indicates the number of nodes in the subtree of the current node. The calculation method is as follows: size= Number of left subtrees + 1 + number of right subtrees

We will continue using the Map interface defined in the previous article implementing Maps based on Arrays or linked lists

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(); }Copy the code

The query

The simplest and most direct way to find a key in a binary tree is to use recursion. Compare the key with the key of the node. If the key is small, continue the recursive search in the left subtree; if the key is large, continue the recursive search in the right subtree

Code implementation:

@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; }}Copy the code

The maximum and minimum values are displayed

In binary trees we may often use the maximum and minimum values in the query tree, including our delete operations later, so we need to implement these two methods;

Implementation of the maximum: recurse from the root node along the right subtree until the right subtree is null, and the node at this point is the implementation of the maximum and minimum value: recurse from the root node along the left subtree until the left subtree is null, and the node is the minimum value

@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);
}
Copy the code

insert

From the above implementation, we can see that the query method of binary tree is as simple and efficient as the binary search method of array in the previous part. This is an important feature of binary tree, and the insertion of binary tree is as simple as the query operation. Ideally, the time complexity of both insertion and query operation is log(N).

If the key value of put is larger than that of the current node, the right subtree is recursed. If the key value of put is smaller, the left subtree is recursed. If the key value of put is equal, the node value is updated. If no value is found at the end of the recursion, create a new node and return

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;
}
Copy the code

Size = left subtree. Size + 1 + right subtree. Size

Delete the maximum and minimum values

One of the more troublesome operations in binary trees is the delete operation, so let’s first look at how the delete Max and delete min should be implemented.

Delete the minimum value: similar to the previous implementation to find the minimum value, along the left path has been deep, until the left subtree of a node is null, then the current node is the minimum value, in the recursion to the right subtree of the current node can be returned;

The idea for maximum is similar

The code is as follows:

@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;
}
Copy the code

delete

We can similarly delete nodes that have only one child or none; But what if you need to delete a node with two nodes?

There are two approaches: replace the node to be deleted with the maximum value of the left subtree, and then delete the maximum value of the left subtree. Alternatively, replace the node to be deleted with the minimum value in the right subtree, and then delete the minimum value in the right subtree

Steps:

Retrieves the maximum from the left subtree of the node or the minimum from the right subtree
Replace the current node with a maximum or minimum value
Call delete Max or delete min

Code implementation

@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;
}
Copy the code

Analysis of the

The efficiency of running a Map using a binary tree depends on the shape of the tree, and the shape of the tree depends on the order in which data is entered. In the best case, the binary tree is balanced, so the time complexity of get and PUT is log(N). However, if the inserted data is ordered, the binary tree will become a linked list, and the performance of GET and PUT will be greatly reduced.

Based on this question, we will continue to improve our Map implementation. In the next article, we will learn how to use red-black trees to implement our Map operation, so that the binary tree is approximately balanced regardless of the insertion order

All source code has been put into github repository github.com/silently952…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏

Implement Map based on binary tree

preface

Introduction to binary trees