关于平衡树(捞)
  • 板块学术版
  • 楼主zhangbo1000
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/13 12:49
  • 上次更新2024/10/13 14:47:27
查看原帖
关于平衡树(捞)
760291
zhangbo1000楼主2024/10/13 12:49

昨天突发奇想,试图用以下的方式来维持二叉搜索树的平衡:

当往一个结点的子树中插入时,如果该子树大小大于其兄弟的 22 倍,则选择将该子树的根结点旋转上来而不是递归访问(再特判一下防止死循环)。

我自己写了一下,是能过板题的(评测记录12)甚至表现比我自己写的 treap 还好。

这样的树应该不是平衡的,至少不是强平衡的,那么,它的各种操作的平均时间复杂度和最坏是多少呢?

2024/10/13 12:49
加载中...