# Talk:Binary search tree

The version 10:23, 2 May 2025 is translated into the Chinese Wikipedia with modifications. 深鸣 (talk) 08:48, 11 May 2025 (UTC)

"The complexity analysis of BST shows that, on average, the insert, delete and search takes O(log n) for n nodes"
This is a nontrivial fact and it would be good to have a source which provides a proof of it. (One such source is https://cs.umb.edu/~ryanc/24s/cs624/07-bst.pdf)
Additionally, stronger results on the behavior of "average" BSTs are known. For example, it has been proven that, if H_n is the height of a random BST with n elements then E[H_n] =  a ln n + O (log log n) for a = 4.31107..., and that Var[H_n] = O((log log n)^2). source: https://luc.devroye.org/devroye_reed_1995_variance_height_random_binary_search_tree.pdf 
In my opinion, stronger results, such as the one above, deserve to be mentioned in the article. Grassoc Oremaker (talk) 07:29, 26 September 2025 (UTC)