| Name : perl-Tree-AVL
| |
| Version : 1.077
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : lp155.1.1
| Date : 2023-07-20 20:17:05
|
| Group : Development/Libraries/Perl
| Source RPM : perl-Tree-AVL-1.077-lp155.1.1.src.rpm
|
| Size : 0.05 MB
| |
| Packager : https://www_suse_com/
| |
| Summary : An AVL (balanced binary) tree for time-efficient storage and retrieval o[cut]
|
Description :
AVL Trees are balanced binary trees, first introduced in \"An Algorithm for
the Organization of Information\" by Adelson-Velskii and Landis in 1962.
Balance is kept in an AVL tree during insertion and deletion by maintaining
a \'balance\' factor in each node.
If the subtree rooted at any node in the tree is evenly balanced, the
balance factor for that node will be 0.
When the right-subtree below a node is taller than the left-subtree, the
balance factor will be 1. For the opposite case, the balance factor will be
-1.
If the either subtree below a node is heavier (taller by more than 2
levels) than the other, the balance factor within the node will be set to
(+-)2, and the subtree rooted at that node will be rebalanced.
Re-balancing is done via \'single\' or \'double\' rotations, each of which
takes constant time.
Insertion into an AVL tree will require at most 1 single or double
rotation.
Deletion from an AVL tree may take as much as log(n) rotations in order to
restore balance.
Balanced trees can save time in your programs when used instead of regular
flat data-structures. For example, if you are processing as much as
1,125,899,906,842,624 (a quadrillion) ordered objects, the time (number of
comparisons) required to access one of those objects will be on the order
of 1,125,899,906,842,624 in the worst case if you keep them in a flat data
structure. However, using a balanced tree such as a 2-3 tree, a Red-Black
tree or an AVL tree, the worst-case time (comparisons) required will 50.
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl:/CPAN-T/15.5/noarch |
