algorithm - 实现平衡因子，每个节点仅增加 1 位

Question

在算法导论 - 一种创造性的方法一书中，问题 4.18:

The AVL algorithms that were presented in Section 4.3.4 require balanced factors with three possible values: 1, 0, or -1. To represent three values we need 2 bits. Suggest a method for implementing these algorithms (with only a slight modification) with only 1 extra bit per node.

我通过记录每个节点的高度而不是平衡因子来实现 AVL 树。

但我不知道如何仅用 1 位来表示三个值 (1、0、-1)。我想一定有一些其他信息可以用来表示 1,0,-1，连同 1 位。

谁能帮忙解答这个问题？

Answer 1

如果节点没有两个儿子-你可以计算它否则你可以在儿子身上记住它:一位在左儿子和一位在右儿子。