之前尝试用一种朴素的方式维护二叉搜索树平衡:
插入新的数时,如果即将访问的子树大小超过其兄弟的 x(x>1)x(x>1)x(x>1) 倍,就选择将其旋转上来而不是递归访问。
这样维护的树应该保证不了平衡,但我自己测了一下,可以过板题的(评测记录1,2),甚至运行比我自己写的 treap 还快。
这种写法的时间复杂度(平均&最坏)是多少呢?