二叉树搜索的复杂性
问题描述：
我在查找二进制堆时发现有冲突的信息。据此，https://en.wikipedia.org/wiki/Binary_heap，它是O（n）（编辑：它实际上是O（log n）），根据这个，Search an element in a heap，它是O（n/2）。二叉树搜索的复杂性
答
*对此只是错误的。二进制堆不是为了搜索各个元素而设计的，而是为了访问最小的元素而优化的。例如，这使得他们能够在时间Θ（n）中建造;它们所需的排序并不像二分查找树那样严格。
看起来有人已经更新了*，这很好。感谢您指出了这一点！
一注意 - 术语O（n/2），虽然在技术上是正确的，但被认为是对大O符号的不良使用。 Big-O符号忽略了常数因素，所以O（n/2）与O（n）相同。如果要计算最终要完成的具体操作次数，请避免使用大O符号，并说“需要完全n/2次比较”。
我很抱歉，我的意思是*链接表示它是O（log n）。 –
由于*上提到的* heap属性，真正的二进制堆将是O（n/2）：*如果A是B的父节点，则节点A的密钥相对于节点B的密钥排序在整个堆中应用相同的排序*排序实际上将搜索的努力分成了两半。但是，这种复杂性在图上是线性的，所以它基本上平均为O（n）。二叉搜索树具有有序子元素，并且可以执行复杂度为O（log n）的真二分搜索。 –
如果“搜索”意味着在堆中搜索特定的数据，那么它应该是'O（n）'。我不确定维基页面的实际含义。但通常堆不支持“搜索”操作 - 它们只是没有被设计来做到这一点。也许有人应该修改wiki页面，或者更清楚地说明它。 – WhatsUp