Binary Tree

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

Binary Tree

Table 29 – Time and space requirements for binary tree
operation	time cost;	space cost
Insert	logN+C	2p+t
Find (average item)	logN	0
Change/replace item	2(logN + C)	0
Remove first	logN + C	2p+t (recovered)
Remove last	logN + C	2p+t (recovered)
Remove in middle	logN + C	2p+t (recovered)
Container overhead		(p+i) + N(2p+t)
Comments	Insertion happens based on sort order. Allocation with each insert. replace requires remove/add sequence to maintain order. Does not automatically remain balanced. Numbers above assume a balanced tree.	Costs same as doubly linked list per item