输入关键字序列{90, 80, 100, 70, 85, 9

给定关键字序列{90, 80, 100, 70, 85, 95, 105, 65, 75}，构建AVL树步骤如下： 1. 插入90：此时AVL树只有一个节点，即根节点90。 2. 插入80：80小于90，成为90的左子节点。 3. 插入100：100大于90，成为90的右子节点。 4. 插入70：70小于90，与80比较，70小于80，成为80的左子节点。 5. 插入85：85小于90，与80比较，85大于80，成为80的右子节点。此时以90为根的树左右子树高度差为0（左子树高度2，右子树高度2），树保持平衡。 6. 插入95：95大于90，与100比较，95小于100，成为100的左子节点。整棵树依旧平衡。 7. 插入105：105大于90，与100比较，105大于100，成为100的右子节点。树的平衡未被破坏。 8. 插入65：65小于90，与80比较，小于80，再与70比较，小于70，成为70的左子节点。此时以90为根的树左子树高度为3（90 - 80 - 70 - 65路径），右子树高度为2（90 - 100路径），但高度差为1，树仍平衡。 9. 插入75：75小于90，与80比较，小于80，与70比较，大于70，成为70的右子节点。此时以90为根的树左子树高度为3（90 - 80 - 70 - 65路径或90 - 80 - 70 - 75路径 ），右子树高度为2（90 - 100路径），高度差为1，满足AVL树平衡条件，不需要调整。