【C++】AVL树的简单实现及验证_自己写个avl树,怎么证明成功了

作者：知新_RL | 2024-04-26 17:06:26

踩

自己写个avl树,怎么证明成功了

文章目录

1、什么是AVL树？
2、AVL树部分模块模拟实现

1、什么是AVL树？

AVL树可以是一棵空树
AVL树也可以是一棵具有如下性质的二叉搜索树：
①它的左右子树都是一棵AVL树
②左右子树高度之差（平衡因子）的绝对值不能超过1

在这里插入图片描述

如果一棵二叉搜索树是高度平衡的，那么他就是AVL树。
如果他有n个结点，其高度可以保持在O(log₂n),搜索时时间复杂度也就是O(log₂n)

2、AVL树部分模块模拟实现

2.1 AVL树结点的定义：

AVL树本质上讲，它是一棵二叉搜索树，只不过加上了平衡因子这一限制条件。

也就是说，在插入一个新节点时，我们不仅要考虑结点的插入位置，还需要考虑插入该节点后对于树中其他结点来说，平衡因子是否需要更新。

其中，插入节点的父节点，它的平衡因子一定需要改变。这就要求我们需要能够快速定位到插入节点的父节点。因此，我们对于AVL树结点的结构应定义为孩子双亲表示法

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/492154