使用链表或数组实现BST的性能权衡是什么?

Question

我只是想知道使用链接实现的二叉搜索树和使用数组实现的二叉搜索树之间的性能比率是多少。我只是想知道性能比较。我已经在stackoverflow上看过这个问题了

Answer 1

我不认为你可以实现一个二叉搜索树与数组。二叉搜索树就像一个高级链表。事实上，如果您使用基本的BST(而不是平衡)并输入预排序的数据，您基本上会得到一个链表。