AVL tree
| This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance) |
In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations.
AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.
Task: Implement an AVL tree in the language of choice and provide at least basic operations.
Scheme
Pure functional version. Explanative article in Russian, written by Swizard.
Tcl
<lang tcl>package require TclOO
namespace eval AVL {
oo::class create Tree {
variable root nil class constructor Template:NodeClass AVL::Node { set class [oo::class create Node [list superclass $nodeClass]] set nil [$class create nil "" "" $class] set root [$nil ref] oo::objdefine $nil { method height {} {return 0} method key {} {error "no key possible"} method value {} {error "no value possible"} method destroy {} { # Do nothing } method print {indent increment} { # Do nothing } } } method insert {key {value ""}} { set node [$class new $key $nil $class] $node setValue $value if {$root eq $nil} { set root $node } else { $root insert $node } return $node } method lookup {key} { for {set node $root} {$node ne $nil} {} { if {[$node key] == $key} { return $node } elseif {[$node key] > $key} { set node [$node left] } else { set node [$node right] } } error "no such node" } method print {{indent 0} {increment 1}} { $root print $indent $increment }
}
oo::class create Node {
variable key value left right lh rh 0 refcount class constructor {n nil instanceFactory} { set class $instanceFactory set 0 [expr {$nil eq "" ? [self] : $nil}] set key $n set value {} set left [set right $0] set refcount 0 } method ref {} { incr refcount return [self] } method destroy {} { if {[incr refcount -1] < 1} next } method key {} {return $key} method value {} {return $value} method setValue {newValue} { set value $newValue } method left {args} { if {![llength $args]} {return $left} if {$left ne $0} { return [$left {*}$args] } } method right {args} { if {![llength $args]} {return $right} if {$right ne $0} { return [$right {*}$args] } } method setLeft {node} { $node ref $left destroy set left $node set lh [$left height] return } method setRight {node} { $node ref $right destroy set right $node set rh [$right height] return }
method print {indent increment} { puts [format "%s%s => %s" [string repeat " " $indent] $key $value] incr indent $increment $left print $indent $increment $right print $indent $increment }
method height {} { return [expr {max([$left height], [$right height]) + 1}] } method balance_factor {} { expr {[$left height] - [$right height]} }
method insert {node} { if {$key > [$node key]} { if {$left eq $0} { my setLeft $node } else { $left insert $node } } else { if {$right eq $0} { my setRight $node } else { $right insert $node } } if {[my balance_factor] > 1} { if {[$left balance_factor] < 0} { $left rotateLeft } my rotateRight } elseif {[my balance_factor] < -1} { if {[$right balance_factor] > 0} { $right rotateRight } my rotateLeft } }
method rotateLeft {} { set new [$class new $key $0 $class] set key [$right key] $new setValue $value set value [$right value] set A $left set B [$right left] set C [$right right] $new setLeft $A $new setRight $B my setLeft $new my setRight $C } method rotateRight {} { set new [$class new $key $0 $class] set key [$left key] $new setValue $value set value [$left value] set A [$left left] set B [$left right] set C $right $new setLeft $B $new setRight $C my setLeft $A my setRight $new }
}
}</lang> Demonstrating: <lang tcl>AVL::Tree create tree for {set i 33} {$i < 127} {incr i} {
tree insert $i [string repeat [format %c $i] [expr {1+int(rand()*5)}]]
} tree print for {set i 0} {$i < 10} {incr i} {
set k [expr {33+int((127-33)*rand())}]
puts $k=>[[tree lookup $k] value]
} tree destroy</lang>
- Output:
64 => @@@
48 => 000
40 => (((((
36 => $
34 => """
33 => !!
35 => #####
38 => &&&
37 => %
39 => ''''
44 => ,
42 => **
41 => )))
43 => +++++
46 => .
45 => --
47 => ////
56 => 888
52 => 444
50 => 22222
49 => 1111
51 => 333
54 => 6
53 => 555
55 => 77
60 => <<<<
58 => ::::
57 => 99999
59 => ;
62 => >>>
61 => ===
63 => ??
96 => ``
80 => PPPPP
72 => HHHH
68 => DDD
66 => BBBB
65 => A
67 => CCC
70 => FFF
69 => EEEE
71 => GGG
76 => LL
74 => JJ
73 => III
75 => KKKK
78 => N
77 => MMMMM
79 => OOOOO
88 => XXX
84 => TTTT
82 => R
81 => QQQQ
83 => SSSS
86 => V
85 => UUU
87 => WWW
92 => \\\
90 => Z
89 => YYYYY
91 => [
94 => ^^^^^
93 => ]]]]
95 => _____
112 => pppp
104 => hh
100 => d
98 => bb
97 => aaa
99 => cccc
102 => ff
101 => eeee
103 => gggg
108 => lll
106 => j
105 => iii
107 => kkkkk
110 => nn
109 => m
111 => o
120 => x
116 => ttt
114 => rrrrr
113 => qqqqq
115 => s
118 => vvv
117 => uuuu
119 => wwww
124 => ||||
122 => zzzz
121 => y
123 => {{{
125 => }}}}
126 => ~~~~
53=>555
55=>77
60=><<<<
100=>d
99=>cccc
93=>]]]]
57=>99999
56=>888
47=>////
39=>''''