# 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:

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

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

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

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

```
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:

```
// 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;
}
}
```

```
// 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) {}
};
```

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

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

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

`firstKey, lastKey`

Methods`keys`

Method`selectKey`

and `rank`

MethodsPerformance Issues