是否存在这样一个具有最优高度但不满足AVL条件的BST？
Is there such a BST that has optimal height but does not satisfy the AVL condition?
我很好奇是否可以构造一个二叉搜索树，使其 n 个元素的高度最小，但它不是 AVL 树。
或者换句话说，根据定义，每个高度最小的二叉搜索树也是AVL树吗？
AVL的要求是左右深度最多相差1
N 个元素的最佳 BST，其中 D = ²log N，属性 深度总和最小。效果是每个元素的深度最多为 ceil(D) 深。
要获得最小的深度总和，树必须从上到下填满，因此各个长度的总和最小。
不是最优的 BST - 而不是 AVL:
f
/ \
a q
/ \
n x
/ \ \
j p y
- 元素：8
- 部门：0 + 1 + 1 + 2 + 2 + 3 + 3 + 3 = 15
最佳 BST - 和 AVL：
_ f _
/ \
j q
/ \ / \
a n p x
\
y
- 元素：8
- 部门：0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 = 13
所以不存在非AVL最优BST
我很好奇是否可以构造一个二叉搜索树，使其 n 个元素的高度最小，但它不是 AVL 树。
或者换句话说，根据定义，每个高度最小的二叉搜索树也是AVL树吗？
AVL的要求是左右深度最多相差1
N 个元素的最佳 BST，其中 D = ²log N，属性 深度总和最小。效果是每个元素的深度最多为 ceil(D) 深。
要获得最小的深度总和，树必须从上到下填满，因此各个长度的总和最小。
不是最优的 BST - 而不是 AVL:
f
/ \
a q
/ \
n x
/ \ \
j p y
- 元素：8
- 部门：0 + 1 + 1 + 2 + 2 + 3 + 3 + 3 = 15
最佳 BST - 和 AVL：
_ f _
/ \
j q
/ \ / \
a n p x
\
y
- 元素：8
- 部门：0 + 1 + 1 + 2 + 2 + 2 + 2 + 3 = 13
所以不存在非AVL最优BST