数据结构【AVL树的实现和应用】

推荐阅读:

AVL树(二)之 C++的实现

AVL树

详解 AVL 树(基础篇)

重点理解四种调整方式和失衡的判断方法

四种旋转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BSTree::llTypeRotation(Node *&ptr){//LL型旋转 
Node *t=ptr;
ptr=ptr->left;
t->left=ptr->right;
ptr->right=t;
}
void BSTree::rrTypeRotation(Node *&ptr){//RR型旋转
Node *t=ptr;
ptr=ptr->right;
t->right=ptr->left;
ptr->left=t;
}
void BSTree::rlTypeRotation(Node *&ptr){//RL型旋转
llTypeRotation(ptr->right);
rrTypeRotation(ptr);
}
void BSTree::lrTypeRotation(Node *&ptr){//LR型旋转
rrTypeRotation(ptr->left);
llTypeRotation(ptr);
}

结合推荐博文图片理解

失衡判断

充分利用递归回溯判断何种失衡再调整

  • 可以使用一个树的高度函数,在判断中调用该函数计算高度差再结合其它控制语句判断
  • 可以直接在树的结点设置高度选项,创建的同时更新高度,判断只需要判断结点属性即可不需要使用高度递归函数。

AVL应用课程设计

AVL树的应用

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~