为什么使用节点数据结构而不是数组创建二叉搜索树 (BST)？
Why are Binary Search Trees (BST) created using a node data structure instead of arrays?
我见过的大多数 BST 示例都是这种形式
Class Node {
Node left;
Node right;
Key key;
Value value;
}
但是 BST 看起来像是具有额外约束的特定形式的二叉堆，即左子节点值应小于父节点值，而父节点值应小于右节点值。
使用数组很容易实现二叉堆。为什么不使用数组创建 BST 以确保维护此额外规则？这样做的缺点是什么？
答案很简单：您不能只动态更改数组的大小。
数组的大小不能事后更改。如果您要使用数组，则必须根据添加或删除的内容来扩大或缩小它，这会导致不必要的开销，因为无论何时您都必须将内容从旧数组复制到新数组。
使用引用或指针的节点允许您在插入或将其设置为 null（或类似的东西）如果你删除一个元素，它会给你一个更动态的结构。
我见过的大多数 BST 示例都是这种形式
Class Node {
Node left;
Node right;
Key key;
Value value;
}
但是 BST 看起来像是具有额外约束的特定形式的二叉堆，即左子节点值应小于父节点值，而父节点值应小于右节点值。
使用数组很容易实现二叉堆。为什么不使用数组创建 BST 以确保维护此额外规则？这样做的缺点是什么？
答案很简单：您不能只动态更改数组的大小。
数组的大小不能事后更改。如果您要使用数组，则必须根据添加或删除的内容来扩大或缩小它，这会导致不必要的开销，因为无论何时您都必须将内容从旧数组复制到新数组。
使用引用或指针的节点允许您在插入或将其设置为 null（或类似的东西）如果你删除一个元素，它会给你一个更动态的结构。