关于平衡树
  • 板块学术版
  • 楼主zhangbo1000
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/14 06:31
  • 上次更新2024/10/14 14:08:04
查看原帖
关于平衡树
760291
zhangbo1000楼主2024/10/14 06:31

之前尝试用一种朴素的方式维护二叉搜索树平衡:

插入新的数时,如果即将访问的子树大小超过其兄弟的 x(x>1)x(x>1) 倍,就选择将其旋转上来而不是递归访问。

这样维护的树应该保证不了平衡,但我自己测了一下,可以过板题的(评测记录12),甚至运行比我自己写的 treap 还快。

这种写法的时间复杂度(平均&最坏)是多少呢?

2024/10/14 06:31
加载中...