不平衡二叉搜索树中的搜索操作
Search operation in imbalanced binary search tree
我无法理解也无法想到在不平衡二叉搜索树中的搜索操作可能比在平衡二叉搜索树中更有效的场景。如果二叉搜索树是高度倾斜的，那么它可能会采用链表的形式，此时运行时间复杂度将是O(n)。有没有可能真正发生的情况？我的教授坚持说有一些，但我就是想不出。
在某些情况下，不平衡的树 可能 更好。以下面两棵树为例：
二叉搜索树背后的想法是，如果您同样有可能搜索节点集中的任何值，那么保持树的平衡可以最大限度地减少您必须进行的平均比较次数。
例如，如果我搜索每个值（1、2、3、4、5、6），那么我想搜索左侧的平衡树。在平衡树上执行该搜索序列将导致 (3 + 2 + 3 + 1 + 2 + 3) = 14 次比较。在不平衡树上执行相同的搜索序列将导致 (1 + 2 + 3 + 4 + 5 + 6) = 21 次比较。
但是，如果我知道我需要搜索的值不会均匀分布，而是偏低怎么办？如果我想搜索值 (1, 2, 1, 2, 1, 3) 怎么办？那么哪棵树会提供更好的性能？
在平衡树上执行这些搜索将导致 (3 + 2 + 3 + 2 + 3 + 3) = 16 次比较。还不错，但是在不平衡树上进行相同的搜索序列只会进行 (1 + 2 + 1 + 2 + 1 + 3) = 10 次比较。
这是一个人为的例子，但它表明了解您的数据 和 了解人们可能最常搜索的值可以帮助您选择正确的安排数据以提供更好的性能。
我无法理解也无法想到在不平衡二叉搜索树中的搜索操作可能比在平衡二叉搜索树中更有效的场景。如果二叉搜索树是高度倾斜的，那么它可能会采用链表的形式，此时运行时间复杂度将是O(n)。有没有可能真正发生的情况？我的教授坚持说有一些，但我就是想不出。
在某些情况下，不平衡的树 可能 更好。以下面两棵树为例：
二叉搜索树背后的想法是，如果您同样有可能搜索节点集中的任何值，那么保持树的平衡可以最大限度地减少您必须进行的平均比较次数。
例如，如果我搜索每个值（1、2、3、4、5、6），那么我想搜索左侧的平衡树。在平衡树上执行该搜索序列将导致 (3 + 2 + 3 + 1 + 2 + 3) = 14 次比较。在不平衡树上执行相同的搜索序列将导致 (1 + 2 + 3 + 4 + 5 + 6) = 21 次比较。
但是，如果我知道我需要搜索的值不会均匀分布，而是偏低怎么办？如果我想搜索值 (1, 2, 1, 2, 1, 3) 怎么办？那么哪棵树会提供更好的性能？
在平衡树上执行这些搜索将导致 (3 + 2 + 3 + 2 + 3 + 3) = 16 次比较。还不错，但是在不平衡树上进行相同的搜索序列只会进行 (1 + 2 + 1 + 2 + 1 + 3) = 10 次比较。
这是一个人为的例子，但它表明了解您的数据 和 了解人们可能最常搜索的值可以帮助您选择正确的安排数据以提供更好的性能。