问不平衡二叉树中的搜索操作

EN

在某些情况下，不平衡的树可能会更好。以以下两棵树为例：

​

​

二进制搜索树背后的思想是，如果您同样有可能搜索节点集中的任何值，那么保持树的平衡就会最小化您必须做的平均比较数。

例如，如果我搜索每个值(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比较。

这是一个精心设计的例子，但它表明，了解您的数据和了解人们可能经常搜索的值，可以帮助您为该数据选择正确的安排，以获得更好的性能。