首先说明,这个too young too simple的想法可能会被许多大佬喷(((
众所周知BST是一种十分容易被卡的数据结构,那么,在插入和删除的时候,能不能在经过的每一个节点判断一下左右子树的树高,如果某一边高度超过了另一边且差距不止 111 就一直旋转,比如左子树比右子树高 222 就右旋,如果左子树比右子树高 444 可能要旋转多次。
这个naive想法的期望复杂度应该是 O(logn)O(logn)O(logn) 的,那么能不能把它卡掉呢?如果不能,这种“平衡树”和其它的平衡树性能比起来又如何呢?