OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
 
Re: ,,improve'' readability in tree(3)

From: Peter Valchev (pvalchevsightly.net)
Date: Wed Mar 08 2006 - 16:23:02 CST

> lg -> log

No, the original is correct. lg means log base 2.

> Index: tree.3
> ===================================================================
> RCS file: /cvs/src/share/man/man3/tree.3,v
> retrieving revision 1.12
> diff -u -p -r1.12 tree.3
> --- tree.3 2005/04/16 06:11:35 1.12
> +++ tree.3 2006/03/08 21:34:44
> -173,8 +173,8 the requested nodes move to the top of t
> On the other hand, every lookup causes memory writes.
> .Pp
> The Balance Theorem bounds the total access time for m operations
> -and n inserts on an initially empty tree as O((m + n)lg n).
> -The amortized cost for a sequence of m accesses to a splay tree is O(lg n).
> +and n inserts on an initially empty tree as O((m + n)log n).
> +The amortized cost for a sequence of m accesses to a splay tree is O(log n).
> .Pp
> A splay tree is headed by a structure defined by the
> .Fn SPLAY_HEAD
> -302,8 +302,8 each red node (except for the root) has
> each leaf node is black.
> .El
> .Pp
> -Every operation on a red-black tree is bounded as O(lg n).
> -The maximum height of a red-black tree is 2lg (n+1).
> +Every operation on a red-black tree is bounded as O(log n).
> +The maximum height of a red-black tree is 2log(n+1).
> .Pp
> A red-black tree is headed by a structure defined by the
> .Fn RB_HEAD
>
> --
> Thordur I. Bjornsson
> Humppa!