1

我见过的大多数 BST 示例都是以下形式

Class Node {
    Node left;
    Node right;
    Key key;
    Value value;
 }

但是 BSTs 看起来像是具有额外约束的二进制堆的一种特定形式，即左子值应小于父值，父值应小于右节点值。

使用数组很容易实现二进制堆。为什么不使用数组创建 BST 以确保维护这个额外的规则？这样做有什么缺点？

4

1 回答 1

1

答案很简单：您不能只动态更改数组的大小。

数组的大小不能只是在之后更改。如果您要使用数组，则必须根据添加或删除的内容来放大或缩小它，这将导致不必要的开销，因为无论何时您都必须将内容从旧数组复制到新数组。

使用使用引用或指针的节点允许您在插入或将其设置为（或类似的东西）时相应地（重新）分配left和分配一个新元素，如果您删除一个为您提供更动态结构的元素。rightnull

于 2015-01-25T01:26:08.500 回答