如何构建基于有序线性结构的AVL树？

本文共计1834个文字，预计阅读时间需要8分钟。

通过有序线性结构构造AVL树，博客早期在结构利用有序数组和有序链表构建。使用平衡二叉树（下文使用AVL树表示）是近似正确选择，但深入分析会发现问题。

通过有序线性结构构造AVL树

本博客旨在结局利用有序数组和有序链表构造平衡二叉树（下文使用AVL树代指）问题。

直接通过旋转来构造AVL树似乎是一个不错的选择，但是稍加分析就会发现，这样平白无故做了许多毫无意义的旋转。因为直接通过旋转调整二叉查找树（下文使用BST代指）并没有利用数组或链表本身是有序的信息，进行了大量无意义的操作。

下面通过leetcode两道例题来说明这个问题。

1. 108. 将有序数组转换为二叉搜索树 题目分析

重点的问题在于：如何利用数组的有序信息呢？

首先我们先来观察一个有序数组和一棵AVL树所呈现的关系

我们可以发现数组中间元素恰好是对应AVL树的root节点（若数组长为偶数，可取中间偏左或偏右元，此时左右子树高度差为1）

我们只需要选取中间元素，构造头节点，在递归地构造其左右子树即可。