1
#include <iostream>
2
#include <stack>
3
#include <utility> // For std::pair
4
#include <exception>
5

6
template <typename Key, typename T>
7
struct TreeNode {
8
    std::pair<Key, T> data;
9
    TreeNode* left;
10
    TreeNode* right;
11
    TreeNode* parent;
12

13
    TreeNode(const Key& key, const T& value, TreeNode* parentNode = nullptr)
14
        : data(std::make_pair(key, value)), left(nullptr), right(nullptr), parent(parentNode) {}
15
};

1
template <typename Key, typename T>
2
class MyMap {
3
public:
4
    MyMap() : root(nullptr) {}
5
    ~MyMap() { clear(root); }
6

7
    // 禁止拷贝构造和赋值
8
    MyMap(const MyMap&) = delete;
9
    MyMap& operator=(const MyMap&) = delete;
10

11
    // 插入或更新键值对
12
    void insert(const Key& key, const T& value) {
13
        if (root == nullptr) {
14
            root = new TreeNode<Key, T>(key, value);
15
            return;
16
        }
17

18
        TreeNode<Key, T>* current = root;
19
        TreeNode<Key, T>* parent = nullptr;
20

21
        while (current != nullptr) {
22
            parent = current;
23
            if (key < current->data.first) {
24
                current = current->left;
25
            } else if (key > current->data.first) {
26
                current = current->right;
27
            } else {
28
                // 键已存在，更新值
29
                current->data.second = value;
30
                return;
31
            }
32
        }
33

34
        if (key < parent->data.first) {
35
            parent->left = new TreeNode<Key, T>(key, value, parent);
36
        } else {
37
            parent->right = new TreeNode<Key, T>(key, value, parent);
38
        }
39
    }
40

41
    // 查找元素，返回指向节点的指针
42
    TreeNode<Key, T>* find(const Key& key) const {
43
        TreeNode<Key, T>* current = root;
44
        while (current != nullptr) {
45
            if (key < current->data.first) {
46
                current = current->left;
47
            } else if (key > current->data.first) {
48
                current = current->right;
49
            } else {
50
                return current;
51
            }
52
        }
53
        return nullptr;
54
    }
55

56
    // 删除元素
57
    void erase(const Key& key) {
58
        TreeNode<Key, T>* node = find(key);
59
        if (node == nullptr) return; // 没有找到要删除的节点
60

61
        // 节点有两个子节点
62
        if (node->left != nullptr && node->right != nullptr) {
63
            // 找到中序后继
64
            TreeNode<Key, T>* successor = minimum(node->right);
65
            node->data = successor->data; // 替换数据
66
            node = successor; // 将要删除的节点指向后继节点
67
        }
68

69
        // 节点有一个或没有子节点
70
        TreeNode<Key, T>* child = (node->left) ? node->left : node->right;
71
        if (child != nullptr) {
72
            child->parent = node->parent;
73
        }
74

75
        if (node->parent == nullptr) {
76
            root = child;
77
        } else if (node == node->parent->left) {
78
            node->parent->left = child;
79
        } else {
80
            node->parent->right = child;
81
        }
82

83
        delete node;
84
    }
85

86
    // 清空所有节点
87
    void clear() {
88
        clear(root);
89
        root = nullptr;
90
    }
91

92
    // 获取迭代器
93
    class Iterator {
94
    public:
95
        Iterator(TreeNode<Key, T>* node = nullptr) : current(node) {}
96

97
        std::pair<const Key, T>& operator*() const {
98
            return current->data;
99
        }
100

101
        std::pair<const Key, T>* operator->() const {
102
            return &(current->data);
103
        }
104

105
        // 前置递增
106
        Iterator& operator++() {
107
            current = successor(current);
108
            return *this;
109
        }
110

111
        // 后置递增
112
        Iterator operator++(int) {
113
            Iterator temp = *this;
114
            current = successor(current);
115
            return temp;
116
        }
117

118
        bool operator==(const Iterator& other) const {
119
            return current == other.current;
120
        }
121

122
        bool operator!=(const Iterator& other) const {
123
            return current != other.current;
124
        }
125

126
    private:
127
        TreeNode<Key, T>* current;
128

129
        TreeNode<Key, T>* minimum(TreeNode<Key, T>* node) const {
130
            while (node->left != nullptr) {
131
                node = node->left;
132
            }
133
            return node;
134
        }
135

136
        TreeNode<Key, T>* successor(TreeNode<Key, T>* node) const {
137
            if (node->right != nullptr) {
138
                return minimum(node->right);
139
            }
140

141
            TreeNode<Key, T>* p = node->parent;
142
            while (p != nullptr && node == p->right) {
143
                node = p;
144
                p = p->parent;
145
            }
146
            return p;
147
        }
148
    };
149

150
    Iterator begin() const {
151
        return Iterator(minimum(root));
152
    }
153

154
    Iterator end() const {
155
        return Iterator(nullptr);
156
    }
157

158
private:
159
    TreeNode<Key, T>* root;
160

161
    // 删除树中的所有节点
162
    void clear(TreeNode<Key, T>* node) {
163
        if (node == nullptr) return;
164
        clear(node->left);
165
        clear(node->right);
166
        delete node;
167
    }
168

169
    // 找到最小的节点
170
    TreeNode<Key, T>* minimum(TreeNode<Key, T>* node) const {
171
        if (node == nullptr) return nullptr;
172
        while (node->left != nullptr) {
173
            node = node->left;
174
        }
175
        return node;
176
    }
177

178
    // 找到最大的节点
179
    TreeNode<Key, T>* maximum(TreeNode<Key, T>* node) const {
180
        if (node == nullptr) return nullptr;
181
        while (node->right != nullptr) {
182
            node = node->right;
183
        }
184
        return node;
185
    }
186
};

1
template <typename KeyType, typename ValueType>
2
AVLNode<KeyType, ValueType>* rightRotate(AVLNode<KeyType, ValueType>* y) {
3
    AVLNode<KeyType, ValueType>* x = y->left;
4
    AVLNode<KeyType, ValueType>* T2 = x->right;
5

6
    // 执行旋转
7
    x->right = y;
8
    y->left = T2;
9

10
    // 更新高度
11
    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
12
    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
13

14
    // 返回新的根
15
    return x;
16
}

1
template <typename KeyType, typename ValueType>
2
AVLNode<KeyType, ValueType>* leftRotate(AVLNode<KeyType, ValueType>* x) {
3
    AVLNode<KeyType, ValueType>* y = x->right;
4
    AVLNode<KeyType, ValueType>* T2 = y->left;
5

6
    // 执行旋转
7
    y->left = x;
8
    x->right = T2;
9

10
    // 更新高度
11
    x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
12
    y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
13

14
    // 返回新的根
15
    return y;
16
}

1
template <typename KeyType, typename ValueType>
2
AVLNode<KeyType, ValueType>* insertNode(AVLNode<KeyType, ValueType>* node, const KeyType& key, const ValueType& value) {
3
    // 1. 执行标准的BST插入
4
    if (node == nullptr)
5
        return new AVLNode<KeyType, ValueType>(key, value);
6

7
    if (key < node->key)
8
        node->left = insertNode(node->left, key, value);
9
    else if (key > node->key)
10
        node->right = insertNode(node->right, key, value);
11
    else {
12
        // 如果键已经存在，更新其值
13
        node->value = value;
14
        return node;
15
    }
16

17
    // 2. 更新节点高度
18
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
19

20
    // 3. 获取平衡因子
21
    int balance = getBalance(node);
22

23
    // 4. 根据平衡因子进行旋转
24

25
    // 左左情况
26
    if (balance > 1 && key < node->left->key)
27
        return rightRotate(node);
28

29
    // 右右情况
30
    if (balance < -1 && key > node->right->key)
31
        return leftRotate(node);
32

33
    // 左右情况
34
    if (balance > 1 && key > node->left->key) {
35
        node->left = leftRotate(node->left);
36
        return rightRotate(node);
37
    }
38

39
    // 右左情况
40
    if (balance < -1 && key < node->right->key) {
41
        node->right = rightRotate(node->right);
42
        return leftRotate(node);
43
    }
44

45
    return node;
46
}

1
template <typename KeyType, typename ValueType>
2
AVLNode<KeyType, ValueType>* deleteNode(AVLNode<KeyType, ValueType>* root, const KeyType& key) {
3
    // 1. 执行标准的BST删除
4
    if (root == nullptr)
5
        return root;
6

7
    if (key < root->key)
8
        root->left = deleteNode(root->left, key);
9
    else if (key > root->key)
10
        root->right = deleteNode(root->right, key);
11
    else {
12
        // 节点有一个或没有子节点
13
        if ((root->left == nullptr) || (root->right == nullptr)) {
14
            AVLNode<KeyType, ValueType>* temp = root->left ? root->left : root->right;
15

16
            // 没有子节点
17
            if (temp == nullptr) {
18
                temp = root;
19
                root = nullptr;
20
            }
21
            else // 一个子节点
22
                *root = *temp; // 复制内容
23

24
            delete temp;
25
        }
26
        else {
27
            // 节点有两个子节点，获取中序后继
28
            AVLNode<KeyType, ValueType>* temp = getMinValueNode(root->right);
29
            // 复制中序后继的内容到此节点
30
            root->key = temp->key;
31
            root->value = temp->value;
32
            // 删除中序后继
33
            root->right = deleteNode(root->right, temp->key);
34
        }
35
    }
36

37
    // 如果树只有一个节点
38
    if (root == nullptr)
39
        return root;
40

41
    // 2. 更新节点高度
42
    root->height = 1 + std::max(getHeight(root->left), getHeight(root->right));
43

44
    // 3. 获取平衡因子
45
    int balance = getBalance(root);
46

47
    // 4. 根据平衡因子进行旋转
48

49
    // 左左情况
50
    if (balance > 1 && getBalance(root->left) >= 0)
51
        return rightRotate(root);
52

53
    // 左右情况
54
    if (balance > 1 && getBalance(root->left) < 0) {
55
        root->left = leftRotate(root->left);
56
        return rightRotate(root);
57
    }
58

59
    // 右右情况
60
    if (balance < -1 && getBalance(root->right) <= 0)
61
        return leftRotate(root);
62

63
    // 右左情况
64
    if (balance < -1 && getBalance(root->right) > 0) {
65
        root->right = rightRotate(root->right);
66
        return leftRotate(root);
67
    }
68

69
    return root;
70
}

1
#include <iostream>
2
#include <string>
3
#include <vector>
4

5
// 假设上面的AVLNode结构、辅助函数和AVLMap类已经定义
6

7
int main() {
8
    AVLMap<int, std::string> avlMap;
9

10
    // 插入键值对
11
    avlMap.put(10, "十");
12
    avlMap.put(20, "二十");
13
    avlMap.put(30, "三十");
14
    avlMap.put(40, "四十");
15
    avlMap.put(50, "五十");
16
    avlMap.put(25, "二十五");
17

18
    // 中序遍历
19
    std::vector<std::pair<int, std::string>> traversal = avlMap.inorderTraversal();
20
    std::cout << "中序遍历: ";
21
    for (const auto& pair : traversal) {
22
        std::cout << "(" << pair.first << ", \"" << pair.second << "\") ";
23
    }
24
    std::cout << std::endl;
25

26
    // 查找键
27
    std::string* val = avlMap.get(20);
28
    if (val)
29
        std::cout << "获取键20的值: " << *val << std::endl;
30
    else
31
        std::cout << "键20不存在。" << std::endl;
32

33
    val = avlMap.get(25);
34
    if (val)
35
        std::cout << "获取键25的值: " << *val << std::endl;
36
    else
37
        std::cout << "键25不存在。" << std::endl;
38

39
    val = avlMap.get(60);
40
    if (val)
41
        std::cout << "获取键60的值: " << *val << std::endl;
42
    else
43
        std::cout << "键60不存在。" << std::endl;
44

45
    // 删除键20
46
    avlMap.remove(20);
47
    std::cout << "删除键20后，中序遍历: ";
48
    traversal = avlMap.inorderTraversal();
49
    for (const auto& pair : traversal) {
50
        std::cout << "(" << pair.first << ", \"" << pair.second << "\") ";
51
    }
52
    std::cout << std::endl;
53

54
    return 0;
55
}