有没有一种方法来建立一个平衡二叉搜索树?建立一个平衡二叉搜索树
例子:
1 2 3 4 5 6 7 8 9
5
/\
3 etc
/\
2 4
/
1
我想没有做到这一点,而无需使用更复杂的自平衡树的方法。否则我可以自己做,但有人可能已经这样做:)
感谢您的答案!这是最后的Python代码:
def _buildTree(self, keys):
if not keys:
return None
middle = len(keys) // 2
return Node(
key=keys[middle],
left=self._buildTree(keys[:middle]),
right=self._buildTree(keys[middle + 1:])
)
中位数不太正确的术语。首先,中位数可能不存在于原始数据中。例如,3和4的中位数是3.5。见http://en.wikipedia.org/wiki/Median – 2010-05-24 21:44:55
你是对的。显然(从你参考的维基百科页面)这个词是medoid。我做了一个编辑。 – 2010-05-24 22:02:05