TreeMap-TreeSet 原理

In a Nutshell

The TreeMap structure is a practical application of the binary tree structure.

In the previous article, Common Types of Binary Trees, we introduced binary search trees. Next, I will guide you through implementing a TreeMap and TreeSet structure similar to those in the Java standard library, helping you integrate theory with practice.

However, since this article is still in the basics of data structures, it will only explain the principles of TreeMap/TreeSet. The hands-on implementation of TreeMap/TreeSet is placed after the binary tree series exercises in Implementing TreeMap/TreeSet.

Unlike previous data structures like hash tables or queues, tree-related data structures require strong recursive thinking, making them more challenging. If your understanding of recursion isn't deep enough, learning it now might be difficult and not very meaningful. Even if you manage to understand it after a lot of effort, you might still struggle with practical problems, which can be discouraging.

Therefore, I suggest progressing step-by-step. In the upcoming binary tree exercise section, we'll guide you through developing recursive thinking with over 100 actual algorithm problems. After completing these, you will be able to tackle all binary tree-related algorithm problems with ease. Implementing tree-related data structures will then feel very simple. You might not even need to refer to my code and can implement TreeMap/TreeSet on your own.

Alright, let's get started.

Advantages of Binary Search Trees

In the previous article Common Types of Binary Trees, we introduced the characteristics of Binary Search Trees (BST), which follow the "left smaller, right larger" property:

For each node in the tree, the value of every node in its left subtree is smaller than the value of that node, and the value of every node in its right subtree is larger than the value of that node.

For example, the following tree is a BST:

    7
   / \
  4   9
 / \   \
1   5   10

This "left smaller, right larger" property allows us to quickly find a specific node or all nodes within a certain range in a BST, which is the main advantage of BSTs.

You should have already learned about Binary Tree Traversal. Next, we will use standard binary tree traversal functions combined with a visualization panel to compare the operations of BSTs and ordinary binary trees.

You can expand the two panels below, and click on the line if (targetNode !== null) to intuitively feel the efficiency difference between the two search algorithms:

The scenario shown here is for searching for a target element. As you can see, using the "left smaller, right larger" property of BSTs, we can quickly locate the target node. The ideal time complexity is the height of the tree O(logN), while the ordinary binary tree traversal function requires O(N) time to traverse all nodes.

As for other operations like insertion, deletion, and modification, you need to first find the target node before performing these operations, right? These operations mainly involve modifying pointers, so their time complexity is also O(logN).

Implementation Principles of TreeMap/TreeSet

By looking at the name TreeMap, you should be able to tell that its structure is similar to the previously introduced Hash Table HashMap. Both store key-value pairs. The HashMap stores key-value pairs in a table array, while TreeMap stores key-value pairs in the nodes of a binary search tree.

As for TreeSet, its relationship with TreeMap is similar to the relationship between HashMap and the hash set HashSet. Simply put, TreeSet is just a simple wrapper around TreeMap. Therefore, the following will mainly explain the implementation principles of TreeMap.

The classic TreeNode structure in LeetCode looks like this:

java 🟢

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { this.val = x; }
}

cpp 🤖

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

python 🤖

class TreeNode:
    def __init__(self, x: int):
        self.val = x
        self.left = None
        self.right = None

go 🤖

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

javascript 🤖

var TreeNode = function(x) {
    this.val = x;
    this.left = null;
    this.right = null;
}

We can implement TreeMap by making a slight modification to the classic TreeNode structure:

java 🟢

// Capital K is the type for keys, capital V is the type for values
class TreeNode<K, V> {
    K key;
    V value;

    TreeNode<K, V> left;
    TreeNode<K, V> right;
    TreeNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

cpp 🤖

// Capital K is the type for keys, capital V is the type for values
template <typename K, typename V>
class TreeNode {
public:
    K key;
    V value;
    TreeNode<K, V>* left;
    TreeNode<K, V>* right;
    TreeNode(K key, V value) : key(key), value(value), left(nullptr), right(nullptr) {}
};

python 🤖

class TreeNode:
    def __init__(self, key: K, value: V):
        self.key = key
        self.value = value
        self.left = None
        self.right = None

go 🤖

type TreeNode struct {
    Key   interface{}
    Value interface{}
    Left  *TreeNode
    Right *TreeNode
}

javascript 🤖

class TreeNode {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
    }
}