Joh*_*ohn 2 c algorithm tree binary-tree red-black-tree
如果我有10个元素并以空树开头,那么以big-O表示法将10个元素插入Red Black的复杂性是多少？
它是否会超过O(log 10),因为每次插入元素时,它都必须搜索元素的适当位置,并在祖先节点和子节点之间执行一系列旋转.所以如果我有N个元素并且在红黑树中插入N次,那么它会不会成为O(n log n)？
谢谢你的帮助.
你从不使用带有常数的big-O(除了1),因为O(10)意味着与O(1)或O(128291)完全相同,所以按照惯例,你总是使用O(1)!
那么,让我们看看将K项插入最初空的RB树中的大O是什么.第一次插入是一个恒定的时间,所以称之为O(1); 并且当有X项时X + 1st是O(log(X))时插入(即使你必须向下旋转每一步,它仍然是与log(X)成比例的最坏情况,所以,O(log(X) ),因为"层"或"级别"的数量仅与X成对数增长 - 因为K级别的RB树具有增加为2的K次幂的节点数.
因此,我们希望X的log(X)从2到N(加上一个costant)的总和,恰好等于N的阶乘的对数.每个Stirling的约,即N log(N) - N,在大O项中,它再次归结为N log(N).