数据结构之平衡二叉树

,

一、平衡二叉树

平衡二叉树

  1. 二叉排序树
  2. 任何一个节点的左子树以及右子树都是平衡二叉树
  3. 任何一个节点的左子树与右子树的高度差值的绝对值不能大于1

平衡二叉树与不是平衡二叉树的区别

image-20260125131406836

平衡因子（BF）

  1. 节点的平衡因子为其节点左子树的高度减去其右子树的高度。
    1. 平衡的值一般为：0 1 -1

最小不平衡子树

  1. 二叉树中插入节点时，距离（叶子节点）最近的插入节点后BF值大于1的节点作为根节点的子树。
  2. 从叶子节点开始计算距离

节点失衡

  1. 二叉树插入节点时，出现平衡因子绝对值大于1的最小不平衡子树。
  2. 通过旋转来修正最小不平衡子树。

image-20260125134641114

二、旋转

当出现节点失衡时就需要通过旋转来修正失衡的平衡二叉树

失衡类型（4种）

LL（左左失衡）

  • 插入节点发生在左子树的左侧

image-20260125142156933

RR（右右失衡）

  • 插入节点发生在右子树的右侧

image-20260125142217421

LR（左右失衡）

  • 插入节点发生在左子树的右侧

image-20260125142236568

RL（右左失衡）

  • 插入节点发生在右子树的左侧

image-20260125142301790

旋转方式

单右旋转

旧根节点为新根节点的右子树，新根节点如果存在右子树则转到旧根节点左子树下

image-20260125142908773

单左旋转

旧根节点为新根节点的左子树，新根节点如果存在左子树则转到旧根节点右子树下

image-20260125181359696

左右旋转

image-20260125152110761

右左旋转

image-20260125152132760

模拟旋转

模拟数据：30 20 10 40 50 60 70 100 90 80

image-20260125164536863

三、平衡框架设计

以下框架设计使用C语言实现

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
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct _Node
{
	int value;				//值
	int heigth;				//高度（用来判断是否失衡）
	struct _Node* left;
	struct _Node* rigth;
}Node;

//创建节点
Node* NewNdoe(int value)
{
	Node* node = malloc(sizeof(Node));
	if (node != NULL)
	{
		node->heigth = 1;
		node->value = value;
		node->left = NULL;
		node->rigth = NULL;
	}
	return node;
}

//获取高度
int GetNodeHeigth(Node* node)
{
	if (node == NULL) return NULL;
	return node->heigth;
}

//获取平衡因子
int GetNodeBalanceFactor(Node* node)
{
	return GetNodeHeigth(node->left) - GetNodeHeigth(node->rigth);
}

//左旋转
Node* LeftRotate(Node* oldRoot)
{
	//右节点成为新根节点
	Node* NewRoot = oldRoot->rigth;
	Node* tmpNode = NewRoot->left;
	//旧根节点成为新根节点左子树
	NewRoot->left = oldRoot;
	//如果新根节点存在左子树，则接在旧根节点的右子树上
	oldRoot->rigth = tmpNode;
	//修正节点高度
	oldRoot->heigth = max(GetNodeHeigth(oldRoot->left), GetNodeHeigth(oldRoot->rigth)) + 1;
	NewRoot->heigth = max(GetNodeHeigth(NewRoot->left), GetNodeHeigth(NewRoot->rigth)) + 1;
	return NewRoot;
}

//右旋转
Node* RigthRotate(Node* oldRoot)
{
	//左节点成为新根节点
	Node* NewRoot = oldRoot->left;
	Node* tmpNode = NewRoot->rigth;
	//旧根节点成为新根节点右子树
	NewRoot->rigth = oldRoot;
	//如果新根节点存在右子树，则接在旧根节点的左子树上
	oldRoot->left = tmpNode;
	//修正节点高度
	oldRoot->heigth = max(GetNodeHeigth(oldRoot->left), GetNodeHeigth(oldRoot->rigth)) + 1 ;
	NewRoot->heigth = max(GetNodeHeigth(NewRoot->left), GetNodeHeigth(NewRoot->rigth)) + 1;
	return NewRoot;
}

//插入节点
Node* Insert(Node* Root, int value)
{
	if (Root == NULL) return NewNdoe(value);
	if (value < Root->value)
	{
		Root->left = Insert(Root->left, value);
	}
	else if (value > Root->value)
	{
		Root->rigth = Insert(Root->rigth, value);
	}
	else
	{
		return Root;
	}
	//设置节点高度
	Root->heigth = max(GetNodeHeigth(Root->left), GetNodeHeigth(Root->rigth)) + 1;
	//获取平衡因子
	int balance = GetNodeBalanceFactor(Root);
	//二叉平衡树
	//左左
	if (balance > 1 && value < Root->left->value)
	{
		return RigthRotate(Root);
	}
	//右右
	if (balance < -1 && value > Root->rigth->value)
	{
		return LeftRotate(Root);
	}
	//左右
	if (balance > 1 && value > Root->left->value)
	{
		Root->left = LeftRotate(Root->left);
		return RigthRotate(Root);

	}
	//右左
	if (balance < -1 && value < Root->rigth->value)
	{
		Root->rigth = RigthRotate(Root->rigth);
		return LeftRotate(Root);

	}
	return Root;
}

int main()
{
	Node* Root = NULL;
	Root = Insert(Root, 30);
	Root = Insert(Root, 20);
	Root = Insert(Root, 10);
	Root = Insert(Root, 40);
	Root = Insert(Root, 50);
	Root = Insert(Root, 60);
	Root = Insert(Root, 70);
	Root = Insert(Root, 100);
	Root = Insert(Root, 90);
	Root = Insert(Root, 80);
	printf("%s\r\n", "Hello");
	return 0;
}

运行结果：

image-20260125184512864