平衡二叉树是一棵带有平衡条件的二叉查找树，其删除操作是在二叉查找树的基础上添加平衡调整算法。
二叉查找树的删除操作参见博文：二叉查找树的删除（第七点）
先看一下示意图（）
/二叉查找树的性质让我们可以很方便的查找最小最大键值/
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
| /*查找最小键值节点：直接递归遍历左子树叶子节点*/
AvlNode* AvlTree::findMin(AvlNode *node)
{
if (NULL == node)
return NULL;
else if (NULL == node->leftchild)
return node;
else
return findMin(node->leftchild);
}
/*非递归实现查找最大键值节点*/
AvlNode* AvlTree::findMax(AvlNode *node)
{
if (node != NULL)
{
while (node->rightchild)
node = node->rightchild;
}
return node;
}
void AvlTree::Delete(int val)
{
if(NULL == Root)
return;
else
Delete(Root, val);
}
//节点的删除就是不断的交换数据，更改删除节点，最后定位到叶子节点
//
void AvlTree::Delete(AvlNode *&node, int val)
{
AvlNode *tempnode = NULL;
if(NULL == node)
return;
else if(val < node->data)
Delete(node->leftchild, val);
else if(val > node->data)
Delete(node->rightchild, val);
//find the val
else if(node->leftchild && node->rightchild)
{
tempnode = findMin(node->rightchild);
node->data = tempnode->data;
Delete(node->rightchild, node->data); //理解！待删除节点键值变换
} //此后要删除的键值节点不是val
else
{
if(node->leftchild && (NULL == node->rightchild))
{
tempnode = findMax(node->leftchild);
node->data = tempnode->data;
Delete(node->leftchild, node->data);
}
else if (node->rightchild && (NULL == node->leftchild))
{
tempnode = findMin(node->rightchild);
node->data = tempnode->data;
Delete(node->rightchild, node->data);
}
else
{
delete(node);
node = NULL;
}
}
if (node) //必须添加这个条件，利用递归的力量，调整平衡
{
//平衡判断
if (2 == Height(node->leftchild) - Height(node->rightchild))
{
//情况判断
if (Height(node->leftchild->leftchild) >= Height(node->leftchild->rightchild))
RotationLeftOnce(node);
else
{
RotationRightOnce(node->leftchild);
RotationLeftOnce(node);
}
}
if (2 == Height(node->rightchild) - Height(node->leftchild))
{
if (Height(node->rightchild->rightchild) >= Height(node->rightchild->leftchild))
RotationRightOnce(node);
else
{
RotationLeftOnce(node->rightchild);
RotationRightOnce(node);
}
}
}
}
|
上面的删除操作具体参见：二叉查找树的删除，另外平衡二叉树的查找，遍历与二叉查找树一样。
上面的删除操作具体参见：二叉查找树的删除，另外平衡二叉树的查找，遍历与二叉查找树一样。
二、清空二叉树（析构函数）
1
2
3
4
5
6
7
8
9
10
| void AvlTree::MakeEmpty(AvlNode *&node)
{
if (node)
{
MakeEmpty(node->leftchild);
MakeEmpty(node->rightchild);
delete node;
}
node = NULL;
}
|
三、平衡二叉树时间复杂度分析
平衡二叉树在二叉查找树的基础上添加了旋转算法，但是旋转操作仅仅改变少数指针的指向，耗费常数时间，平衡二叉树加入了平衡机制，所以其深度为logN，查找、插入和删除在平均和最坏情况下都是O(logN)。对比二叉查找树，时间上稳定了很多。