就最坏情况而言,红黑树在其重平衡过程中可能需要对多达W(logn)个节点做重染色。然而,这并不足以代表红黑树在一般情况下的性能。 试证明,就分摊意义而言,红黑树重平衡过程中需重染色的节点不超过(1)个。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题