[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: tech_(_at_)_openbsd_(_dot_)_org*Subject*: ,,improve'' readability in tree(3)*From*: "Thordur I. Bjornsson" <thib_(_at_)_mi_(_dot_)_is>*Date*: Wed, 8 Mar 2006 21:36:40 +0000*Mail-followup-to*: tech_(_at_)_openbsd_(_dot_)_org

lg -> log 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!

**Follow-Ups**:**Re: ,,improve'' readability in tree(3)***From:*Peter Valchev

- Prev by Date:
**dhcpclient diff (new options)** - Next by Date:
**Re: ,,improve'' readability in tree(3)** - Previous by thread:
**dhcpclient diff (new options)** - Next by thread:
**Re: ,,improve'' readability in tree(3)** - Index(es):