Flo*_*ire 1 random big-o time-complexity binary-search-tree data-structures
我已经知道如果你试图找到具有特定键的项目,最坏情况的运行时间是O(n),n节点的数量.如果您尝试按其键的顺序打印出所有数据项,则最坏情况的运行时间为O(n).如果您尝试搜索特定数据项(您不知道密钥),则最坏情况的运行时间为O(n).但是,如果键和数据都是整数,则输入项在插入之前随机加扰.最糟糕的运行时间是否仍然相同？
在最坏的情况下,是的.随机构建的具有n个节点的BST具有2 n-1/n!建造简并的机会,这是非常罕见的,因为n达到任何合理的尺寸但仍然可能.在这种情况下,查找可能需要Θ(n)时间,因为搜索可能需要一直下降到最深的叶子.
但是,在期望中,树高将为Θ(log n),因此查找将花费预期的O(log n)时间.
顺便说一句,打印树的时间与树的形状无关.它总是Θ(n).
希望这可以帮助!