1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

bool insert(const T& data) {
    // 首先按照 二叉搜索树的方式 查找插入位置并插入节点
    if (_root == nullptr) {
        // 树为空 插入节点 直接将新节点作为树的根
        _root = new Node(data);
        _root->_bf = 0;		// 只有根节点的树, 根节点平衡因子为 0

        return true;		// 插入成功, 直接返回
    }

    // 走到这里就说明需要 查找插入位置 了
    Node* cur = _root;	// 从根节点开始比较
    Node* parent = nullptr;	// 需要记录父亲节点 供插入时连接
    while (cur) {
        // 循环结束的条件是 cur为空, cur为空时就说明 插入位置找到了
        if (cur->_data > data) {
            // 插入值比当前节点值 小, 则向左孩子找
            parent = cur;
            cur = cur->_pLeft;
        }
        else if (cur->_data < data) {
            // 插入值比当前节点值 大, 则向右孩子找
            parent = cur;
            cur = cur->_pRight;
        }
        else {
            // 走到这里 说明数中已存在相同数据
            return false;
        }
    }

    // 出循环之后, cur 即为数据需要插入的位置
    cur = new Node(data);
    // 将cur与树连接起来
    if (data > parent->_data) {
        parent->_pRight = cur;		// 插入数据比父亲节点数据大, 则插入到父亲节点的右孩子
    }
    else if (data < parent->_data) {
        parent->_pLeft = cur;			// 插入数据比父亲节点数据小, 则插入到父亲节点的左孩子
    }
    // 三叉链结构, cur节点虚存储父亲节点
    cur->_pParent = parent;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

// cur 是插入后的新节点
cur->_pParent = parent;

while (parent) {
    if (cur == parent->_pLeft)
        parent->_bf--;			// 新节点在父亲节点的左孩子, 则父亲节点的左子树高度+1, 则父亲节点的平衡因子-1
    else
        parent->_bf++;

    // 更新完之后, 就需要判断 需要继续更新 还是停止更新 或是调整平衡
    if (parent->_bf == 0) {
        // 不会再影响更上边的节点, 可以结束
        break;
    }
    else if (parent->_bf == -1 || parent->_bf == 1) {
        // 可能会继续影响更高节点的平衡 所以需要更新parent 和 cur, 进而继续更新祖先节点的平衡因子
        cur = cur->_pParent;
        parent = parent->_pParent;
    }
    else if (parent->_bf == -2 || parent->_bf == 2) {
        // 需要调整平衡了
    }
    else {
        // 以上情况都是在 保证树已经是AVL树时 插入新节点
        // 如果不是 则会走到此处 触发断言 进而发现错误
        assert(false);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

void RotateL(Node* parent) {
	Node* subR = parent->_pRight;		// 即 不平衡节点的右孩子
	Node* subRL = subR->_pLeft;			// 不平衡节点的右孩子 的 左孩子

	/* parent 可能是 整棵树的根, 也可能是某节点的子树根
	* 而 由于AVL树的节点是三叉链的结构, 所以改变节点的位置 需要改变此节点的父亲节点, 所以
	* 当 parent 是整棵树的根时, 即parent->_pParent 为空, 那么左旋时 就需要直接将 subR改为整棵树的根
	* 当 parent 是某节点的子树时, 就需要将 parent->_pParent 与 subR 连接起来
	* 所以 需要将 parent->_pParent 存储起来
	*/
	Node* ppNode = parent->_pParent;

	// 不平衡节点的右孩子的左孩子 变为 父亲节点的右孩子, 并将 父亲节点 变为 此节点的左孩子
	// 并记得 链接三叉链
	parent->_pRight = subRL;
	if (subRL)
		subRL->_pParent = parent;

	subR->_pLeft = parent;
	parent->_pParent = subR;

	// 改变不平衡节点 的 父亲节点的指向
	if (parent == _root) {
		_root = subR;
		_root->_pParent = nullptr;
	}
	else {
		if (parent == ppNode->_pLeft)		// 不平衡节点是其父亲节点的左孩子
			ppNode->_pLeft = subR;			// 把 subR 连接到 其父亲节点的左孩子上
		else
			ppNode->_pRight = subR;			// 把 subR 连接到 其父亲节点的右孩子上

		subR->_pParent = ppNode;		// 更新 subR 的父亲节点
	}

	parent->_bf = 0;
	subR->_bf = 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void RotateR(Node* parent) {
	Node* subL = parent->_pLeft;		// 不平衡节点的左孩子
	Node* subLR = subL->_pRight;		// 不平衡节点的左孩子 的 右孩子

	Node* ppNode = parent->_pParent;

	// 将 不平衡节点的左孩子的的右孩子 变为 父亲节点的左孩子, 并将 父亲节点 变为 此节点的右孩子
	// 并记得 链接三叉链
	parent->_pLeft = subLR;
	if (subLR)			// 右孩子不为空才链接父亲节点
		subLR->_pParent = parent;

	subL->_pRight = parent;
	parent->_pParent = subL;

	// 改变不平衡节点 的 父亲节点的指向
	if (parent == _root) {
		_root = subL;
		_root->_pParent = nullptr;
	}
	else {
		if (parent == ppNode->_pLeft)		// 不平衡节点是其父亲节点的左孩子
			ppNode->_pLeft = subL;			// 把 subL 连接到 其父亲节点的左孩子上
		else
			ppNode->_pRight = subL;			// 把 subL 连接到 其父亲节点的右孩子上

		subL->_pParent = ppNode;		// 更新 subL 的父亲节点
	}

	parent->_bf = 0;
	subL->_bf = 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

void RotateLR(Node* parent) {
	Node* subL = parent->_pLeft;		// 不平衡节点的左孩子
	Node* subLR = subL->_pRight;		// 不平衡节点的左孩子的右孩子
	int bf = subLR->_bf;
	// 左右双旋
	RotateL(parent->_pLeft);
	RotateR(parent);

	// 画图可以看出来 如果插入的位置不同 平衡因子的更新规则也不同
	if (bf == 0) {
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1) {
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1) {
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else {
		assert(false);
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216

public:
	bool insert(const T& data) {
		// 首先按照 二叉搜索树的方式 查找插入位置并插入节点
		if (_root == nullptr) {
			// 树为空 插入节点 直接将新节点作为树的根
			_root = new Node(data);
			_root->_bf = 0;		// 只有根节点的树, 根节点平衡因子为 0

			return true;		// 插入成功, 直接返回
		}

		// 走到这里就说明需要 查找插入位置 了
		Node* cur = _root;	// 从根节点开始比较
		Node* parent = nullptr;	// 需要记录父亲节点 供插入时连接
		while (cur) {
			// 循环结束的条件是 cur为空, cur为空时就说明 插入位置找到了
			if (cur->_data > data) {
				// 插入值比当前节点值 小, 则向左孩子找
				parent = cur;
				cur = cur->_pLeft;
			}
			else if (cur->_data < data) {
				// 插入值比当前节点值 大, 则向右孩子找
				parent = cur;
				cur = cur->_pRight;
			}
			else {
				// 走到这里 说明数中已存在相同数据
				return false;
			}
		}

		// 出循环之后, cur 即为数据需要插入的位置
		cur = new Node(data);
		// 将cur与树连接起来
		if (data > parent->_data) {
			parent->_pRight = cur;		// 插入数据比父亲节点数据大, 则插入到父亲节点的右孩子
		}
		else if (data < parent->_data) {
			parent->_pLeft = cur;			// 插入数据比父亲节点数据小, 则插入到父亲节点的左孩子
		}
        
		// 三叉链结构, cur节点虚存储父亲节点
		cur->_pParent = parent;
		while (parent) {
			if (cur == parent->_pLeft)
				parent->_bf--;			// 新节点在父亲节点的左孩子, 则父亲节点的左子树高度+1, 则父亲节点的平衡因子-1
			else
				parent->_bf++;

			// 更新完之后, 就需要判断 需要继续更新 还是停止更新 或是调整平衡了
			if (parent->_bf == 0) {
				// 某祖先节点的平衡因子 从 -1 或 1 -> 0, 说明 插入新节点使此祖先节点的左右子树高度相等了
				// 不会再影响更上边的节点, 所以可以结束
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1) {
				cur = cur->_pParent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2) {
				// 左单旋的情况
				if (parent->_bf == 2 && cur->_bf == 1) {
					RotateL(parent);
				}
				// 右单旋的情况
				else if (parent->_bf == -2 && cur->_bf == -1) {
					RotateR(parent);
				}
				// 左右双旋的情况
				else if (parent->_bf == -2 && cur->_bf == 1) {
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1) {
					RotateRL(parent);
				}

				break;
			}
			else {
				// 以上情况都是在保证插入新节点时, 树已经是平衡二叉搜索树
				// 如果不是 则会走到此处 触发断言 进而发现错误
				assert(false);
			}
		}
		
		return true;
	}

private:
	void RotateL(Node* parent) {
		Node* subR = parent->_pRight;		// 此节点, 即不平衡节点的右孩子
		Node* subRL = subR->_pLeft;			// 此节点左孩子

		/* parent 可能是 整棵树的根, 也可能是某节点的子树根
		* 而 由于AVL树的节点是三叉链的结构, 所以改变节点的位置 需要改变此节点的父亲节点, 所以
		* 当 parent 是整棵树的根时, 即parent->_pParent 为空, 那么左旋时 就需要直接将 subR改为整棵树的根
		* 当 parent 是某节点的子树时, 就需要将 parent->_pParent 与 subR 连接起来
		* 所以 需要将 parent->_pParent 存储起来
		*/
		Node* ppNode = parent->_pParent;

		// 将 此节点的左孩子 变为 父亲节点的右孩子, 并将 此节点的父亲节点 变为 此节点的左孩子
		// 并记得 链接三叉链
		parent->_pRight = subRL;
		if (subRL)
			subRL->_pParent = parent;

		subR->_pLeft = parent;
		parent->_pParent = subR;

		// 改变不平衡节点 的 父亲节点的指向
		if (parent == _root) {
			_root = subR;
			_root->_pParent = nullptr;
		}
		else {
			if (parent == ppNode->_pLeft)		// 不平衡节点是其父亲节点的左孩子
				ppNode->_pLeft = subR;			// 把 subR 连接到 其父亲节点的左孩子上
			else
				ppNode->_pRight = subR;			// 把 subR 连接到 其父亲节点的右孩子上

			subR->_pParent = ppNode;		// 更新 subR 的父亲节点
		}

		parent->_bf = 0;
		subR->_bf = 0;
	}

	void RotateR(Node* parent) {
		Node* subL = parent->_pLeft;		// 此节点, 即不平衡节点的左孩子
		Node* subLR = subL->_pRight;		// 此节点右孩子

		Node* ppNode = parent->_pParent;
        
		parent->_pLeft = subLR;
		if (subLR)
			subLR->_pParent = parent;

		subL->_pRight = parent;
		parent->_pParent = subL;

		// 改变不平衡节点 的 父亲节点的指向
		if (parent == _root) {
			_root = subL;
			_root->_pParent = nullptr;
		}
		else {
			if (parent == ppNode->_pLeft)		// 不平衡节点是其父亲节点的左孩子
				ppNode->_pLeft = subL;			// 把 subL 连接到 其父亲节点的左孩子上
			else
				ppNode->_pRight = subL;			// 把 subL 连接到 其父亲节点的右孩子上

			subL->_pParent = ppNode;		// 更新 subL 的父亲节点
		}

		parent->_bf = 0;
		subL->_bf = 0;
	}

	void RotateLR(Node* parent) {
		Node* subL = parent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;
		// 左右双旋
		RotateL(parent->_pLeft);
		RotateR(parent);
		
		// 画图可以看出来 如果插入的位置不同 平衡因子的更新规则也不同
		if (bf == 0) {
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1) {
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1) {
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else {
			assert(false);
		}
	}

	void RotateRL(Node* parent) {
		Node* subR = parent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;
		// 右左双旋
		RotateR(parent->_pRight);
		RotateL(parent);
		
		if (bf == 0) {
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == 1) {
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1) {
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else {
			assert(false);
		}
	}