二叉搜索树插入方法的java时间复杂度
你好
我有一个关于二元搜索树插入方法的时间复杂性的问题。我读了一些关于这个问题的答案，但有些答案彼此不同。二叉搜索树插入方法在平均情况下的时间复杂度是O（logn），在最坏情况下的时间复杂度是O（n）？或者是O（n logn）表示平均情况，O（n^2）表示最坏情况？在平均情况下，什么时候变成O（n logn），在最坏情况下变成O（n^2）
你可以在下面搜索框中键入要查询的问题!
你好
我有一个关于二元搜索树插入方法的时间复杂性的问题。我读了一些关于这个问题的答案，但有些答案彼此不同。二叉搜索树插入方法在平均情况下的时间复杂度是O（logn），在最坏情况下的时间复杂度是O（n）？或者是O（n logn）表示平均情况，O（n^2）表示最坏情况？在平均情况下，什么时候变成O（n logn），在最坏情况下变成O（n^2）
# 1 楼答案
在avg情况下，对于1个插入操作，是O（logn），因为它包括一个测试（恒定时间）和一个递归调用（访问树中总节点数的一半），使得问题在恒定时间内更小。因此，对于n个插入操作，平均情况为O（nlogn）。关键是操作所需的时间与树的高度成比例。平均而言，1次插入操作为O（logn），但在最坏的情况下，高度为O（n） 如果您正在进行n次操作，则平均值为O（nlgn），最差值为O（n^2）