当前位置:   article > 正文

【数据结构】平衡二叉树(AVL树)

【数据结构】平衡二叉树(AVL树)

目录

前言

一、AVL树概念

二、AVL树节点定义

 三、AVL树插入

1. 按照二叉搜索树的方式插入新节点

2. 维护节点的平衡因子与调整树的结构

 a. 新节点插入较高左子树的左侧---左左:右单旋

b. 新节点插入较高右子树的右侧---右右:左单旋

c. 新节点插入较高左子树的右侧---左右:先左单旋再右单旋 

d. 新节点插入较高右子树的左侧---右左:先右单旋再左单旋

四、AVL树删除

附录:AVL树实现参考代码 


前言

二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查 找元素相当于在顺序表中搜索元素,效率低下。

因此,两位俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种方法,用以解决上述问题。


一、AVL树概念

AVL 树是一种平衡二叉树,得名于其发明者的名字( Adelson-Velskii 以及 Landis)。(可见名字长的好处,命名都能多占一个字母出来)。平衡二叉树递归定义如下:

  • 左右子树的高度差小于等于 1。
  • 其每一个子树均为平衡二叉树。

 为了使AVL树保持平衡,在节点中增加了一个平衡因子作为节点属性。当树发生变化时,就通过维护平衡因子与改变树的结构来使树保持平衡。

二、AVL树节点定义

  1. template<class K, class V>
  2. struct AVLTreeNode
  3. {
  4. AVLTreeNode<K, V>* _left;
  5. AVLTreeNode<K, V>* _right;
  6. AVLTreeNode<K, V>* _parent;
  7. std::pair<K, V> _kv;
  8. int _bf; //balance factor
  9. AVLTreeNode(const std::pair<K, V>& kv)
  10. :_left(nullptr)
  11. , _right(nullptr)
  12. , _parent(nullptr)
  13. , _kv(kv)
  14. , _bf(0)
  15. {}
  16. };

 三、AVL树插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步:

1. 按照二叉搜索树的方式插入新节点

参考二叉搜索树。

【数据结构】二叉搜索树-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/lyhv_v/article/details/139243506

2. 维护节点的平衡因子与调整树的结构

 cur插入后,pParent的平衡因子一定需要调整,在插入之前,pParent 的平衡因子分为三种情况:-1,0, 1, 分以下两种情况:

  1. 如果pCur插入到pParent的左侧,只需给pParent的平衡因子-1即可
  2. 如果pCur插入到pParent的右侧,只需给pParent的平衡因子+1即可

此时:pParent的平衡因子可能有三种情况:0,正负1, 正负2

  1. 如果pParent的平衡因子为0,说明插入之前pParent的平衡因子为正负1,插入后被调整成0,此时满足 AVL树的性质,插入成功
  2. 如果pParent的平衡因子为正负1,说明插入前pParent的平衡因子一定为0,插入后被更新成正负1,此 时以pParent为根的树的高度增加,需要继续向上更新
  3. 如果pParent的平衡因子为正负2,则pParent的平衡因子违反平衡树的性质,需要对其进行旋转处理

 a. 新节点插入较高左子树的左侧---左左:右单旋

  1. Node* RotateR(Node* parent)
  2. {
  3. Node* sub = parent->_left;
  4. Node* subR = sub->_right;
  5. if (parent == _root)
  6. {
  7. _root = sub;
  8. sub->_parent = nullptr;
  9. }
  10. else
  11. {
  12. Node* up = parent->_parent;
  13. if (up->_kv.first > sub->_kv.first)
  14. up->_left = sub;
  15. else
  16. up->_right = sub;
  17. sub->_parent = up;
  18. }
  19. parent->_left = subR;
  20. if (subR != nullptr)
  21. subR->_parent = parent;
  22. sub->_right = parent;
  23. parent->_parent = sub;
  24. parent->_bf = 0;
  25. sub->_bf = 0;
  26. return sub;
  27. }

b. 新节点插入较高右子树的右侧---右右:左单旋

  1. Node* RotateL(Node* parent)
  2. {
  3. Node* sub = parent->_right;
  4. Node* subL = sub->_left;
  5. if (parent == _root)
  6. {
  7. _root = sub;
  8. sub->_parent = nullptr;
  9. }
  10. else
  11. {
  12. Node* up = parent->_parent;
  13. if (up->_kv.first > sub->_kv.first)
  14. up->_left = sub;
  15. else
  16. up->_right = sub;
  17. sub->_parent = up;
  18. }
  19. parent->_right = subL;
  20. if (subL != nullptr)
  21. subL->_parent = parent;
  22. sub->_left = parent;
  23. parent->_parent = sub;
  24. parent->_bf = 0;
  25. sub->_bf = 0;
  26. return sub;
  27. }

c. 新节点插入较高左子树的右侧---左右:先左单旋再右单旋 

  1. Node* RotateLR(Node* parent)
  2. {
  3. Node* child = parent->_left;
  4. Node* sub = child->_right;
  5. Node* subL = sub->_left;
  6. Node* subR = sub->_right;
  7. if (parent == _root)
  8. {
  9. _root = sub;
  10. sub->_parent = nullptr;
  11. }
  12. else
  13. {
  14. Node* up = parent->_parent;
  15. if (up->_kv.first > sub->_kv.first)
  16. up->_left = sub;
  17. else
  18. up->_right = sub;
  19. sub->_parent = up;
  20. }
  21. sub->_right = parent;
  22. parent->_parent = sub;
  23. sub->_left = child;
  24. child->_parent = sub;
  25. parent->_left = subR;
  26. if (subR != nullptr)
  27. subR->_parent = parent;
  28. child->_right = subL;
  29. if (subL != nullptr)
  30. subL->_parent = child;
  31. if (sub->_bf == 1)
  32. {
  33. parent->_bf = 0;
  34. child->_bf = -1;
  35. }
  36. else if (sub->_bf == -1)
  37. {
  38. parent->_bf = 1;
  39. child->_bf = 0;
  40. }
  41. else
  42. {
  43. parent->_bf = 0;
  44. child->_bf = 0;
  45. }
  46. sub->_bf = 0;
  47. return sub;
  48. }

d. 新节点插入较高右子树的左侧---右左:先右单旋再左单旋

  1. Node* RotateRL(Node* parent)
  2. {
  3. Node* child = parent->_right;
  4. Node* sub = child->_left;
  5. Node* subL = sub->_left;
  6. Node* subR = sub->_right;
  7. if (parent == _root)
  8. {
  9. _root = sub;
  10. sub->_parent = nullptr;
  11. }
  12. else
  13. {
  14. Node* up = parent->_parent;
  15. if (up->_kv.first > sub->_kv.first)
  16. up->_left = sub;
  17. else
  18. up->_right = sub;
  19. sub->_parent = up;
  20. }
  21. sub->_left = parent;
  22. parent->_parent = sub;
  23. sub->_right = child;
  24. child->_parent = sub;
  25. parent->_right = subL;
  26. if (subL != nullptr)
  27. subL->_parent = parent;
  28. child->_left = subR;
  29. if (subR != nullptr)
  30. subR->_parent = child;
  31. if (sub->_bf == 1)
  32. {
  33. parent->_bf = -1;
  34. child->_bf = 0;
  35. }
  36. else if (sub->_bf == -1)
  37. {
  38. parent->_bf = 0;
  39. child->_bf = 1;
  40. }
  41. else
  42. {
  43. parent->_bf = 0;
  44. child->_bf = 0;
  45. }
  46. sub->_bf = 0;
  47. return sub;
  48. }

四、AVL树删除

因为AVL树也是二叉搜索树,可按照二叉搜索树的方式将节点删除,然后再更新平衡因子,只不 错与删除不同的时,删除节点后的平衡因子更新,最差情况下一直要调整到根节点的位置。

具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

附录:AVL树实现参考代码 

AVLTree · 梁羽赫/cpp_advanced - 码云 - 开源中国 (gitee.com)icon-default.png?t=N7T8https://gitee.com/yuhe-liang/cpp_advanced/tree/master/AVLTree

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/703566
推荐阅读
相关标签
  

闽ICP备14008679号