1 .\"
2 .\" This file and its contents are supplied under the terms of the
3 .\" Common Development and Distribution License ("CDDL"), version 1.0.
4 .\" You may only use this file in accordance with the terms of version
5 .\" 1.0 of the CDDL.
6 .\"
7 .\" A full copy of the text of the CDDL should have accompanied this
8 .\" source. A copy of the CDDL is also available via the Internet at
9 .\" http://www.illumos.org/license/CDDL.
10 .\"
11 .\"
12 .\" Copyright 2015 Joyent, Inc.
13 .\"
14 .Dd May 07, 2015
15 .Dt LIBAVL 3LIB
16 .Os
17 .Sh NAME
18 .Nm libavl
19 .Nd generic self-balancing binary search tree library
20 .Sh SYNOPSIS
21 .Lb libavl
22 .In sys/avl.h
23 .Sh DESCRIPTION
24 The
25 .Nm
26 library provides a generic implementation of AVL trees, a form of
27 self-balancing binary tree. The interfaces provided allow for an
28 efficient way of implementing an ordered set of data structures and, due
29 to its embeddable nature, allow for a single instance of a data
30 structure to belong to multiple AVL trees.
31 .Lp
32 Each AVL tree contains entries of a single type of data structure.
33 Rather than allocating memory for pointers for those data structures,
34 the storage for the tree is embedded into the data structures by
67 .Pp
68 Note, insertions into an AVL tree always result in an ordered tree.
69 Insertions into a linked list do not guarantee order. If order is
70 required, then the time to do the insertion into a linked list will
71 depend on the time of the search algorithm being employed to find the
72 place to insert at.
73 .Ed
74 .It Sy Delete One Node
75 .Bd -filled -compact
76 Deleting a single node from a linked list is
77 .Sy O(1),
78 whereas deleting a single node from an AVL tree takes
79 .Sy O(log(n))
80 time.
81 .Ed
82 .It Sy Delete All Nodes
83 .Bd -filled -compact
84 Deleting all nodes from a linked list is
85 .Sy O(n) .
86 With an AVL tree, if using the
87 .Xr avl_delete_nodes 3AVL
88 function then deleting all nodes
89 is
90 .Sy O(n) .
91 However, if iterating over each entry in the tree and then removing it using
92 a while loop,
93 .Xr avl_first 3AVL
94 and
95 .Xr avl_remove 3AVL
96 then the time to remove all nodes is
97 .Sy O(n\ *\ log(n)).
98 .Ed
99 .It Sy Visit the Next or Previous Node
100 .Bd -filled -compact
101 Visiting the next or previous node in a linked list is
102 .Sy O(1) ,
103 whereas going from the next to the previous node in an AVL tree will
104 take between
105 .Sy O(1)
106 and
107 .Sy O(log(n)) .
|
1 .\"
2 .\" This file and its contents are supplied under the terms of the
3 .\" Common Development and Distribution License ("CDDL"), version 1.0.
4 .\" You may only use this file in accordance with the terms of version
5 .\" 1.0 of the CDDL.
6 .\"
7 .\" A full copy of the text of the CDDL should have accompanied this
8 .\" source. A copy of the CDDL is also available via the Internet at
9 .\" http://www.illumos.org/license/CDDL.
10 .\"
11 .\"
12 .\" Copyright 2015 Joyent, Inc.
13 .\"
14 .Dd Dec 04, 2015
15 .Dt LIBAVL 3LIB
16 .Os
17 .Sh NAME
18 .Nm libavl
19 .Nd generic self-balancing binary search tree library
20 .Sh SYNOPSIS
21 .Lb libavl
22 .In sys/avl.h
23 .Sh DESCRIPTION
24 The
25 .Nm
26 library provides a generic implementation of AVL trees, a form of
27 self-balancing binary tree. The interfaces provided allow for an
28 efficient way of implementing an ordered set of data structures and, due
29 to its embeddable nature, allow for a single instance of a data
30 structure to belong to multiple AVL trees.
31 .Lp
32 Each AVL tree contains entries of a single type of data structure.
33 Rather than allocating memory for pointers for those data structures,
34 the storage for the tree is embedded into the data structures by
67 .Pp
68 Note, insertions into an AVL tree always result in an ordered tree.
69 Insertions into a linked list do not guarantee order. If order is
70 required, then the time to do the insertion into a linked list will
71 depend on the time of the search algorithm being employed to find the
72 place to insert at.
73 .Ed
74 .It Sy Delete One Node
75 .Bd -filled -compact
76 Deleting a single node from a linked list is
77 .Sy O(1),
78 whereas deleting a single node from an AVL tree takes
79 .Sy O(log(n))
80 time.
81 .Ed
82 .It Sy Delete All Nodes
83 .Bd -filled -compact
84 Deleting all nodes from a linked list is
85 .Sy O(n) .
86 With an AVL tree, if using the
87 .Xr avl_destroy_nodes 3AVL
88 function then deleting all nodes
89 is
90 .Sy O(n) .
91 However, if iterating over each entry in the tree and then removing it using
92 a while loop,
93 .Xr avl_first 3AVL
94 and
95 .Xr avl_remove 3AVL
96 then the time to remove all nodes is
97 .Sy O(n\ *\ log(n)).
98 .Ed
99 .It Sy Visit the Next or Previous Node
100 .Bd -filled -compact
101 Visiting the next or previous node in a linked list is
102 .Sy O(1) ,
103 whereas going from the next to the previous node in an AVL tree will
104 take between
105 .Sy O(1)
106 and
107 .Sy O(log(n)) .
|