平衡二叉树的增加修改删除以及树的自旋

发表于 | 分类于

平衡二叉树的增加修改删除以及树的自旋

平衡二叉树

AVL树：所有节点的左子树的高度差不超过1的二叉树。查询效率非常高。

右单旋

1
2
3
4
5
//       k2              k1
//       /              /  \
//      k1      ->     N    k2
//     /  
//    N

(1)将k1的右子树保存在k2的左子树总
(2)将k1的右子树置位k2

左单旋

1
2
3
4
5
//    k2                  k1
//     \                /    \
//      k1     ->      k2     N
//       \
//        N

(1)将k1的左子树保存在k2的右子树中
(2)将k1的左子树置位k2

右左旋

1
2
3
4
5
//     k2           k2                 N
//      \            \                / \
//      k1    ->      N      ->     k2    k1
//      /              \  
//     N               k1

当造成不平衡的为右子树，并且右子树的左子树比较高：
先以k2的右子树为根节点右旋，再以k2位根节点左旋。

左右旋

1
2
3
4
5
//     k2             k2             N
//     /             /              / \
//    k1    ->      N      ->     k1   k2
//     \           /  
//      N         k1

当造成不平衡的为左子树，并且左子树的右子树比较高：
先以k2的左子树为根节点左旋，再以k2位根节点右旋。

平衡二叉树的类的定义与实现

平衡二叉树类的定义

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
class AVLTree {
public:
	AVLTree();
	~AVLTree();
	
	typedef struct _NODE {
		int nData;
		_NODE* pLeft;
		_NODE* pRight;
	}NODE,*PNODE;

	//向一个二叉树中添加一个数据
	//参数0：要插入的数据
	//参数1：错误码
	bool Insert(int nEle, int& nError);
	//从一个二叉树中删除一个数据
	//参数0：要删除的数据
	//参数1：错误码
	bool Delete(int nEle, int& nError);
	//前序遍历
	void PreOrder();
	//中序遍历
	void InOrder();
	//后序遍历
	void PostOrder();
private:
	//向一个二叉树中添加一个数据
	//参数0：是要添加的数据
	//参数1：是要插入的子树
	//参数2：用于得到一个错误码
	bool InsertNode(int nEle, PNODE& pNode, int& nError);
	//向一个二叉树中删除一个数据
	//参数0：是要被删除的数据
	//参数1：要被删除节点的子树
	//参数2：用于得到一个错误码
	bool DeleteNode(int nEle, PNODE& pTree, int& nError);
	//获取一个子树的高度
	//参数：要获取树的子树
	int GetHeight(PNODE pTree);
	//获取一个子树的最大值
	//参数：用于得到最大值
	bool GetMax(PNODE pTree, int& nMax);
	//获取一个子树的最小值
	//参数：用于得到最小值
	bool GetMin(PNODE pTree, int& nMin);
	//以此节点为圆心左旋
	//参数：要旋转的节点
	bool SingleL(PNODE& pNode);
	//以此节点为圆心右旋
	//参数：要旋转的节点
	bool SingleR(PNODE& pNode);
	//以此节点为圆心左右旋
	//参数：要旋转的节点
	bool DoubleLR(PNODE& pNode);
	//以此节点为圆心右左旋
	//参数：要旋转的节点
	bool DoubleRL(PNODE& pNode);

	void PreOrderTraverse(PNODE& pNode);
	void InOrderTraverse(PNODE& pNode);
	void PostOrderTraverse(PNODE& pNode);
private:
	PNODE m_pRoot;
};

平衡二叉树的插入

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
//函数名：Insert
//作用：向树中插入一个数据
//参数0：是要添加的数据
//参数1：用于得到一个错误码
//返回值：用于判断次函数是否执行成功
//说明：
bool AVLTree::Insert(int nEle,int& nError) {
	return InsertNode(nEle, m_pRoot, nError);
}
//函数名：InsertNode
//作用：向一个二叉树中插入一个数据
//参数0：是要添加的数据
//参数1：是要插入的子树
//参数2：用于得到一个错误码
//返回值：用于判断次函数是否执行成功
//说明：
bool AVLTree::InsertNode(int nEle, PNODE& pNode, int& nError) {
	bool bSuccess = true;
	//1 判断是够是要插入的节点
	if (pNode == NULL) {
		pNode = new NODE;
		pNode->pLeft = nullptr;
		pNode->pRight = nullptr;
		pNode->nData = nEle;
		return true;
	}
	//2 判断要插入的数据和当前根节点比较大小
	if (nEle > pNode->nData) {
		bSuccess = InsertNode(nEle, pNode->pRight, nError);
	}
	else if (nEle < pNode->nData) {
		bSuccess = InsertNode(nEle, pNode->pLeft, nError);
	}
	else {
		return false;
	}
	if (bSuccess == false) {
		return bSuccess;
	}
	//3 判断一下经历了插入之后，本节点是否平衡？
	int nLHeight = GetHeight(pNode->pLeft);
	int nRHeight = GetHeight(pNode->pRight);
	int nSub = nLHeight - nRHeight;
	//3.1 如果左边高
	if (nSub == 2) {
		nLHeight = GetHeight(pNode->pLeft->pLeft);
		nRHeight = GetHeight(pNode->pLeft->pRight);
		//3.1.1 需要右旋
		//       k2              k1
		//       /              /  \
		//      k1      ->     N    k2
		//     /  
		//    N  
		if (nLHeight >= nRHeight) {
			SingleR(pNode);
		}
		//3.1.2 需要左右旋
		//     k2             k2             N
		//     /             /              / \
		//    k1    ->      N      ->     k1   k2
		//     \           /  
		//      N         k1  
		else {
			DoubleLR(pNode);
		}
	}
	//3.2 如果是右边高
	else if (nSub == -2) {
		nLHeight = GetHeight(pNode->pRight->pLeft);
		nRHeight = GetHeight(pNode->pRight->pRight);
		//3.2.1 需要左旋
		//    k2                  k1
		//     \                /    \
		//      k1     ->      k2     N
		//       \
		//        N
		if (nLHeight <= nRHeight) {
			SingleL(pNode);
		}
		//3.2.2 需要右左旋
		//     k2           k2                 N
		//      \            \                / \
		//      k1    ->      N      ->     k2    k1
		//      /              \  
		//     N               k1  
		else {
			DoubleRL(pNode);
		}
	}
	return true;
}

平衡二叉树的深度

1
2
3
4
5
6
7
8
9
10
11
12
13
//函数名：GetHeight
//作用：获取子树的高度
//参数0：要获取的树
//返回值：用于得到树的高度
//说明：
int AVLTree::GetHeight(PNODE pTree) {
	if (pTree == nullptr) {
		return 0;
	}
	int nLeftHeight = GetHeight(pTree->pLeft);
	int nRightHeight = GetHeight(pTree->pRight);
	return (nLeftHeight > nRightHeight ? nLeftHeight : nRightHeight) + 1;
}

平衡二叉树的删除

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
//平衡二叉树的删除
bool AVLTree::Delete(int nEle, int& nError) {
	return DeleteNode(nEle, m_pRoot, nError);
}
//函数名：DeleteNode
//作用：从二叉树中删除掉一个数据
//参数0：是要被删除的数据
//参数1：要删除节点的子树
//参数2：用于得到一个错误码
//返回值：bool
//说明：
bool AVLTree::DeleteNode(int nEle, PNODE& pTree, int& nError) {
	bool bSuccess = true;
	//1 判断节点是否为空
	if (pTree == NULL) {
		return false;
	}
	//2 判断要删除的数据比当前子树的根节点大，在右子树中继续删除
	if (nEle > pTree->nData) {
		bSuccess = DeleteNode(nEle, pTree->pRight, nError);
	}
	//3 判断要删除的数据比当前子树的根节点小，在左子树中继续删除
	else if (nEle < pTree->nData) {
		bSuccess = DeleteNode(nEle, pTree->pLeft, nError);
	}
	//4 判断要删除的数据和当前子树的根节点一样大，应该删除
	else {
		//4.1 要删除的点是一个叶子节点
		if (pTree->pLeft == nullptr&&pTree->pRight == nullptr) {
			delete pTree;
			pTree = nullptr;
			return true;
		}
		//4.2 要删除的点是一个树干
		//4.2.1 分别获取此节点的左子树高和右子树高
		int nLeftHeight = GetHeight(pTree->pLeft);
		int nRightHeight = GetHeight(pTree->pRight);
		//4.2.2 判断一下，这两颗数谁高
		if (nLeftHeight > nRightHeight) {
			//左边高，直接获取左子树的最大值，之后赋值，并到左子树中删除最大值
			int nMax = 0;
			GetMax(pTree->pLeft, nMax);
			pTree->nData = nMax;
			bSuccess = DeleteNode(nMax, pTree->pLeft, nError);
		}
		else {
			//右边高，直接获取右子树的最小值，之后赋值，并到右子树中删除最小值
			int nMin = 0;
			GetMin(pTree->pRight, nMin);
			pTree->nData = nMin;
			bSuccess = DeleteNode(nMin, pTree->pRight, nError);
		}
	}
	if (bSuccess == false) {
		return bSuccess;
	}
	//5 判断一下经历了删除之后，本节点是否平衡？
	int nLHeight = GetHeight(pTree->pLeft);
	int nRHeight = GetHeight(pTree->pRight);
	int nSub = nLHeight - nRHeight;
	//5.1 如果左边高
	if (nSub == 2) {
		nLHeight = GetHeight(pTree->pLeft->pLeft);
		nRHeight = GetHeight(pTree->pLeft->pRight);
		//5.1.1 需要右旋
		//       k2              k1
		//       /              /  \
		//      k1      ->     N    k2
		//     /  
		//    N  
		if (nLHeight > nRHeight) {
			SingleR(pTree);
		}
		//5.1.2 需要左右旋
		//     k2             k2             N
		//     /             /              / \
		//    k1    ->      N      ->     k1   k2
		//     \           /  
		//      N         k1  
		else {
			DoubleLR(pTree);
		}
	}
	//5.2 如果是右边高
	else if (nSub == -2) {
		nLHeight = GetHeight(pTree->pRight->pLeft);
		nRHeight = GetHeight(pTree->pRight->pRight);
		//5.2.1 需要左旋
		//    k2                  k1
		//     \                /    \
		//      k1     ->      k2     N
		//       \
		//        N
		if (nLHeight <= nRHeight) {
			SingleL(pTree);
		}
		//5.2.2 需要右左旋
		//     k2           k2                 N
		//      \            \                / \
		//      k1    ->      N      ->     k2    k1
		//      /              \  
		//     N               k1  
		else {
			DoubleRL(pTree);
		}
	}
	return true;
}

最大子树与最小子树

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
//函数名：GetMax
//作用：获取树的最大值
//参数0：要获取的树
//参数1：用于得到最大值
//返回值：用于判断函数是否执行成功
//说明：
bool AVLTree::GetMax(PNODE pTree, int& nMax) {
	if (pTree == NULL) {
		return false;
	}
	while (pTree)
	{
		nMax = pTree->nData;
		pTree = pTree->pRight;
	}
	return true;
}

//函数名：GetMin
//作用：获取树的最小值
//参数0：要获取的树
//参数1：用于得到最小值
//返回值：用于判断函数是否执行成功
//说明：
bool AVLTree::GetMin(PNODE pTree, int& nMin) {
	if (pTree == NULL) {
		return false;
	}
	while (pTree)
	{
		nMin = pTree->nData;
		pTree = pTree->pLeft;
	}
	return true;
}

平衡二叉树的遍历

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
//前序遍历整棵树
void AVLTree::PreOrder() {
	PreOrderTraverse(m_pRoot);
}
//中序遍历整棵树
void AVLTree::InOrder() {
	InOrderTraverse(m_pRoot);
}
//后序遍历整棵树
void AVLTree::PostOrder() {
	PostOrderTraverse(m_pRoot);
}
void AVLTree::PreOrderTraverse(PNODE& pNode) {
	if (pNode == NULL)
		return;
	printf("%d\n", pNode->nData);
	PreOrderTraverse(pNode->pLeft);
	PreOrderTraverse(pNode->pRight);
}

void AVLTree::InOrderTraverse(PNODE& pNode) {
	if (pNode == NULL)
		return;
	InOrderTraverse(pNode->pLeft);
	printf("%d\n", pNode->nData);
	InOrderTraverse(pNode->pRight);
}

void AVLTree::PostOrderTraverse(PNODE& pNode) {
	if (pNode == NULL)
		return;
	PostOrderTraverse(pNode->pLeft);
	PostOrderTraverse(pNode->pRight);
	printf("%d\n", pNode->nData);
}

平衡二叉树的旋转

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
//函数名：SingleL
//作用：以此节点为圆心左旋
//参数0：要旋转的节点
//返回值：判断此函数是否成功
bool AVLTree::SingleL(PNODE& pNode) {
	//    k2                  k1
	//     \                /    \
	//      k1     ->      k2     N
	//       \
	//        N
	//将k1的左子树保存在k2的右子树中
	//将k1的左子树置为k2
	PNODE k2 = pNode;
	PNODE k1 = pNode->pRight;
	k2->pRight = k1->pLeft;
	k1->pLeft = k2;
	pNode = k1;
	return true;
}
//函数名：SingleR
//作用：以此节点为圆心右旋
//参数0：要旋转的节点
//返回值：判断此函数是否成功
bool AVLTree::SingleR(PNODE& pNode) {
	//       k2              k1
	//       /              /  \
	//      k1      ->     N    k2
	//     /  
	//    N  
	//将k1的右子树保存在k2的左子树中
	//将k1的右子树置为k2
	PNODE k2 = pNode;
	PNODE k1 = pNode->pLeft;
	k2->pLeft = k1->pRight;
	k1->pRight = k2;
	pNode = k1;
	return true;
}
//函数名：DoubleLR
//作用：以此节点为圆心左右旋
//参数0：要旋转的节点
//返回值：判断此函数是否成功
bool AVLTree::DoubleLR(PNODE& pNode) {
	//     k2             k2             N
	//     /             /              / \
	//    k1    ->      N      ->     k1   k2
	//     \           /  
	//      N         k1  
	SingleL(pNode->pLeft);
	SingleR(pNode);
	return true;
}
//函数名：DoubleRL
//作用：以此节点为圆心右左旋
//参数0：要旋转的节点
//返回值：判断此函数是否成功
bool AVLTree::DoubleRL(PNODE& pNode) {
	//     k2           k2                 N
	//      \            \                / \
	//      k1    ->      N      ->     k2    k1
	//      /              \  
	//     N               k1  
	SingleR(pNode->pRight);
	SingleL(pNode);
	return true;
}