RWBTree, RWBTreeDictionary

SourcePro Core : Essential Tools Module User's Guide : Appendix A, Choosing a Collection : Time and Space Considerations : RWBTree, RWBTreeDictionary

RWBTreeOnDisk has complexity similar to RWBTreeDictionary, but the time overhead is much greater since “following linked nodes” becomes “disk seek;” and the size overhead has a much greater impact on disk storage than on core memory.

Table 31 – Time and space requirements for RWBTree and RWBTreeDictionary
operation	time cost	space cost
Insert	logN+C	2p + t + small (fully amortized)
Find (average item)	logN	0
Change/replace item	2logN+2 or C	0
Remove first	2logN(log2(ORDER))+C (worst case)	2p+t (recovered)
Remove last	2logN(log2(ORDER))+C (worst case)	2p+t (recovered)
Remove in middle	2logN(log2(ORDER))+C (worst case)	2p+t (recovered)
Container overhead	Re-balance may occur at each insert or remove. However it will happen less often than for a balanced binary tree.	This depends on how fully the nodes are packed. Each node costs ORDER(2p+t+1)+i and there will be no more than 2N/ORDER, and no fewer than min(N/ORDER,1) nodes. Inserting presorted items will tend to maximize the size. Sedgewick says the size is close to 1.44 N/ORDER for random data
Comments	Insertion based on sort order. The logarithm is approximately base ORDER which is the splay of the b-tree. (In fact the base is between ORDER and 2ORDER depending on the actual loading of the b-tree) Replace for b-tree requires remove then insert. For btreedictionary the value is copied in place