二進制搜索樹搜索操作

Question

我想知道一個二叉搜索樹有效搜索它必須是真實的。

Answer 1

爲了高效地搜索二叉搜索樹，該樹必須是平衡的。也就是說，每個節點的左右子樹具有大致相同數量的子節點。當二叉搜索樹完全平衡時，搜索它是O（log n）操作。另一方面，退化樹具有右（或左）子樹上的所有節點。搜索就像搜索鏈接列表：O（n）。

查看維基百科相關文章，Binary search tree，瞭解更多信息。