在 AVL 树中拆分后子树的大小

Question

所以我试图在 AVL 树中实现拆分方法（给定一个带有键 X 的节点拆分树..）并且因为我只有 AVL 树 class 的大小字段，所以我不能找到一种方法来找到分裂后每个子树的大小。我正在考虑为每个节点添加一个大小字段，但这个解决方案现在太复杂了，因为我将不得不编辑我编写的许多代码。 我很乐意提供解决方案（如果存在，在这些条件下）知道如何在拆分后找到每个子树的大小（时间复杂度不超过 O(logn)）。谢谢！

Answer 1

如果不向节点附加额外数据，则无法在亚线性时间内确定拆分每一侧的大小。