简单的不平衡搜索树的平均渐近深度是多少? [英] What is the average asymptotic depth of a simple unbalanced search tree?

问题描述

对于平衡的搜索树，在所有情况下均为O(log(N)).对于不平衡的搜索树，最坏的情况是O(N)，例如，插入1、2、3、4...最佳情况下的复杂度是在平衡时，例如，插入6、4、8、3、5 7 .如何定义不平衡搜索树的平均用例复杂度?

解决方案

二叉树的平均高度为Theta(sqrt(n)).在以下论文中已经显示(或引用，但不是很确定): 解决方案

The average height of Binary Trees is Theta(sqrt(n)). This has been shown (or referenced, not very sure) in the following paper: http://www.dtc.umn.edu/~odlyzko/doc/arch/extreme.heights.pdf.

But perhaps you are more interested in the average depth of a random node and this is Theta(log n), as can be seen here: http://www.toves.org/books/data/ch05-trees/index.html (Section 5.2.4).

这篇关于简单的不平衡搜索树的平均渐近深度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！