【淼】萌新求助,关于BST
  • 板块灌水区
  • 楼主Stinger
  • 当前回复13
  • 已保存回复13
  • 发布时间2021/2/13 11:54
  • 上次更新2023/11/5 03:19:50
查看原帖
【淼】萌新求助,关于BST
361308
Stinger楼主2021/2/13 11:54

首先说明,这个too young too simple的想法可能会被许多大佬喷(((

众所周知BST是一种十分容易被卡的数据结构,那么,在插入和删除的时候,能不能在经过的每一个节点判断一下左右子树的树高,如果某一边高度超过了另一边且差距不止 11 就一直旋转,比如左子树比右子树高 22 就右旋,如果左子树比右子树高 44 可能要旋转多次。

这个naive想法的期望复杂度应该是 O(logn)O(logn) 的,那么能不能把它卡掉呢?如果不能,这种“平衡树”和其它的平衡树性能比起来又如何呢?

2021/2/13 11:54
加载中...