昨天突发奇想,试图用以下的方式来维持二叉搜索树的平衡:
当往一个结点的子树中插入时,如果该子树大小大于其兄弟的 222 倍,则选择将该子树的根结点旋转上来而不是递归访问(再特判一下防止死循环)。
我自己写了一下,是能过板题的(评测记录1,2)甚至在数据未加强的板题上表现比我写的 treap 还好。
这样的树应该不是平衡的,至少不是强平衡的,那么,它的各种操作的平均时间复杂度和最坏是多少呢?