37 Lookup One Node
38 Lookup of a single node in a linked list is O(n), whereas lookup
39 of a single node in an AVL tree is O(log(n)).
40
41 Insert One Node
42 Inserting a single node into a linked list is O(1). Inserting a
43 single node into an AVL tree is O(log(n)).
44
45 Note, insertions into an AVL tree always result in an ordered
46 tree. Insertions into a linked list do not guarantee order. If
47 order is required, then the time to do the insertion into a
48 linked list will depend on the time of the search algorithm being
49 employed to find the place to insert at.
50
51 Delete One Node
52 Deleting a single node from a linked list is O(1), whereas
53 deleting a single node from an AVL tree takes O(log(n)) time.
54
55 Delete All Nodes
56 Deleting all nodes from a linked list is O(n). With an AVL tree,
57 if using the avl_delete_nodes(3AVL) function then deleting all
58 nodes is O(n). However, if iterating over each entry in the tree
59 and then removing it using a while loop, avl_first(3AVL) and
60 avl_remove(3AVL) then the time to remove all nodes is
61 O(n * log(n)).
62
63 Visit the Next or Previous Node
64 Visiting the next or previous node in a linked list is O(1),
65 whereas going from the next to the previous node in an AVL tree
66 will take between O(1) and O(log(n)).
67
68 In general, AVL trees are a good alternative for linked lists when order
69 or lookup speed is important and a reasonable number of items will be
70 present.
71
72 INTERFACES
73 The shared object libavl.so.1 provides the public interfaces defined
74 below. See Intro(3) for additional information on shared object
75 interfaces. Individual functions are documented in their own manual
76 pages.
77
349
350 INTERFACE STABILITY
351 Committed
352
353 MT-Level
354 See Locking.
355
356 SEE ALSO
357 Intro(3), pthread_atfork(3C)
358
359 avl_add(3AVL), avl_create(3AVL), avl_destroy(3AVL),
360 avl_destroy_nodes(3AVL), avl_find(3AVL), avl_first(3AVL),
361 avl_insert(3AVL), avl_insert_here(3AVL), avl_is_empty(3AVL),
362 avl_last(3AVL), avl_nearest(3AVL), avl_numnodes(3AVL), avl_remove(3AVL),
363 avl_swap(3AVL),
364
365 Adel'son-Vel'skiy, G. M. and Landis, Ye. M., An Algorithm for the
366 Organization of Information, No. 2, Vol. 16, 263-266, Deklady Akademii
367 Nauk, USSR, Moscow, 1962.
368
369 illumos May 7, 2015 illumos
|
37 Lookup One Node
38 Lookup of a single node in a linked list is O(n), whereas lookup
39 of a single node in an AVL tree is O(log(n)).
40
41 Insert One Node
42 Inserting a single node into a linked list is O(1). Inserting a
43 single node into an AVL tree is O(log(n)).
44
45 Note, insertions into an AVL tree always result in an ordered
46 tree. Insertions into a linked list do not guarantee order. If
47 order is required, then the time to do the insertion into a
48 linked list will depend on the time of the search algorithm being
49 employed to find the place to insert at.
50
51 Delete One Node
52 Deleting a single node from a linked list is O(1), whereas
53 deleting a single node from an AVL tree takes O(log(n)) time.
54
55 Delete All Nodes
56 Deleting all nodes from a linked list is O(n). With an AVL tree,
57 if using the avl_destroy_nodes(3AVL) function then deleting all
58 nodes is O(n). However, if iterating over each entry in the tree
59 and then removing it using a while loop, avl_first(3AVL) and
60 avl_remove(3AVL) then the time to remove all nodes is
61 O(n * log(n)).
62
63 Visit the Next or Previous Node
64 Visiting the next or previous node in a linked list is O(1),
65 whereas going from the next to the previous node in an AVL tree
66 will take between O(1) and O(log(n)).
67
68 In general, AVL trees are a good alternative for linked lists when order
69 or lookup speed is important and a reasonable number of items will be
70 present.
71
72 INTERFACES
73 The shared object libavl.so.1 provides the public interfaces defined
74 below. See Intro(3) for additional information on shared object
75 interfaces. Individual functions are documented in their own manual
76 pages.
77
349
350 INTERFACE STABILITY
351 Committed
352
353 MT-Level
354 See Locking.
355
356 SEE ALSO
357 Intro(3), pthread_atfork(3C)
358
359 avl_add(3AVL), avl_create(3AVL), avl_destroy(3AVL),
360 avl_destroy_nodes(3AVL), avl_find(3AVL), avl_first(3AVL),
361 avl_insert(3AVL), avl_insert_here(3AVL), avl_is_empty(3AVL),
362 avl_last(3AVL), avl_nearest(3AVL), avl_numnodes(3AVL), avl_remove(3AVL),
363 avl_swap(3AVL),
364
365 Adel'son-Vel'skiy, G. M. and Landis, Ye. M., An Algorithm for the
366 Organization of Information, No. 2, Vol. 16, 263-266, Deklady Akademii
367 Nauk, USSR, Moscow, 1962.
368
369 illumos December 4, 2015 illumos
|