Re: [9front] New Balanced Search Tree Implementation

[Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2900 bytes --]

On Sun, Dec 11, 2016 at 10:30 PM, Benjamin Purcell <benjapurcell@gmail.com>
wrote:

> I have written a binary search tree C library for Plan 9.  It contains
> implementations of both left leaning red-black trees and AVL trees.
> In short, you create an AVL tree with
>
> Bsttree *t = bstcreate(AVL, cmp);
>
> and an LLRB tree with
>
> Bsttree *t = bstcreate(LLRB, cmp);
>
> Cmp is a comparison function.  All other implementation details are
> hidden from the user.
>
> I intend to replace libavl with this library for the following reasons
> (details can be found below):
>
> 1. You get a choice of BST with a single API.
> 2. The AVL implementation is much faster.
> 3. The AVL implementation is smaller and less complicated.
> 4. The API is easier to use.
>
> Item 1. is self-explanatory.
>
> Item 2.
> Measurements of the new AVL implementation against the old one shows
> that on average:
> Insertion is 21.9% faster.
> Deletion is 23.9% faster.
> Lookup is 14.95% faster.
> 10 trials were conducted on random keys.  Sequential keys show similar
> results.
>
> Item 3.
> As for code size, the new AVL implementation plus walk code -- which
> is shared with the LLRB tree -- comes to 362 source lines of idiomatic
> C. The old AVL implementation 436 lines.  The old implementation also
> contains more functions, and calls many of them unnecessarily.
> Despite the fact that it has more functions, the individual functions
> themselves are more complicated.
>
> Item 4.
> The AVL implementation's api has the following signatures expressed as
> abstract types:
>
> Avl *(*)(Avltree*, Avl*);
> Avl *(*)(Avltree*, Avl*, int);
> Avl *(*)(Avlwalk*);
> Avltree *(*)(int(*)(Avl*, Avl*));
> Avlwalk *(*)(Avltree*);
> void (*)(Avltree*, Avl*, Avl**);
> void (*)(Avlwalk*);
>
> Duplicate signatures have been removed in the above.  The new bst
> implementation has the following de-duped signatures:
>
> Bst *(*)(Bsttree*);
> Bsttree *(*)(int, int(*cmp)(Bst*, Bst*));
> Channel *(*)(Bsttree*, Bst*, Bst*, int);
>
> but maintains the same functionality.  Which API would you rather use?
>
> The code can be found at the following locations:
>
> /n/contrib/spew/libbst
> https://bitbucket.org/spewspews/libbst
> https://github.com/spewspews/libbst
>
> A full man page is include and various tests are included in src/tests
> including measurements of AVL vs. LLRB, and the new AVL implementation
> against the old.
>
> If there are no objections I would like to remove libavl and add
> libbst instead.  Libavl has no usages in the source tree.  If anyone tries
> to compile a libavl program then tough.  There will be a better
> implementation available and we can always keep it available in
> contrib or extra.
>
> Spew
>




There is no license information file in

https://github.com/spewspews/libbst


means , it can not be used in any way  or manner .



Thank you very much .


Mehmet Erol Sanliturk

[-- Attachment #2: Type: text/html, Size: 3976 bytes --]