面试官提到的 AVL 树

也会有很大的影响，尤其是当树的形态结构变成一个链条结构的时候，查询最后一个元素的效率极底，如何解决这个问题呢?

关键在于如何最大限度的减小树的深度，从而提高查询效率，正是基于这一点，平衡二叉查找树出现了!

平衡二叉查找树，算法由Adel'son-Vel'skii和 Landis两位大神发明，同时也俗称AVL 树，来自两位大神的姓名缩写，特性如下：

• 它的左子树和右子树都是平衡二叉树;
• 且它的左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1;

简单的说，就是为了保证平衡，当前节点的左子树、右子树的高度差不超过1!

废话也不多说了，直奔主题，算法思路如下!

二、算法思路

平衡二叉查找树的查找思路，与二叉树是一样，每次查询的时候对半分，只查询一部分，以达到提供效率的目的，插入、删除也一样，最大的不同点：每次插入或者删除之后，需要计算节点高度，然后按需进行调整!

如何调整呢?主要方法有：左旋转、右旋转!

下面我们分别来分析一下插入、删除的场景调整。

2.1、插入场景

我们来分析一下插入的场景，如下：

场景一

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!