On Wed, Feb 08, 2006 at 09:34:02PM -0200, Gustavo Rios wrote: > Don't get me wrong, i am very confident with openbsd. > > Although i am very confident using the openbsd native support for my > needs, all of them have some thing i dislike. > > First: i would really enjoy worst case O(log2 n), none of the method i > know so far make such garantee. Another problem is about memory usage: > They all requires 3 pointer (left/right node and the element pointer) > plus space for thing like left/right subtree weight, color, etc. >
Have you actually looked at the link I posted? "...it can search, insert, and delete in O(log n) time, where n is the number of elements in the tree." log here is the log of base 2. > I could see a paradise for the following scenario: worst case > search/delete/insert in O(log2 N) and space requirement O(3N). > > Is that possible? Any suggestions? > There is a good reason why there are three pointers -- stack usage. tree(3) is doing non recursive tree operations to keep the stack usage low -- stack space is very limited in kernel space. You could go recursive to save the parent pointer. Oh and your space requirement is wrong. Btw. I doubt that you can find a algorithm that does search/delete/insert in O(log2 N) without an additional state/depth stored on a per node basis. -- :wq Claudio
