AVL tree: Difference between revisions
→{{header|Scheme}}
Line 11,020:
(else))</lang>
{{out}}
The demonstration is randomized. The following is an example of one run.
The ‘pretty printed’ tree is a diagonal reflection of the usual from-the-root-downwards, left-to-right representation. It goes from-the-root-rightwards, top-to-bottom.
<pre>$ csc -DDEMONSTRATION -R r7rs -X r7rs avl_trees-scheme.scm && ./avl_trees-scheme
----------------------------------------------------------------------
keys = (12 16 20 6 9 18 15 10 13 4 2 7 11 5 8 3 19 14 17 1)
----------------------------------------------------------------------
(1, 1.0) depth = 4 bal = 0
(2, 2.0) depth = 3 bal = 0
(3, 3.0) depth = 4 bal = 0
(4, 4.0) depth = 2 bal = -1
(5, 5.0) depth = 3 bal = 0
(6, 6.0) depth = 1 bal = 0
(7, 7.0) depth = 3 bal = 1
(8, 8.0) depth = 4 bal = 0
(9, 9.0) depth = 2 bal = 0
(10, 10.0) depth = 3 bal = 1
(11, 11.0) depth = 4 bal = 0
(12, 12.0) depth = 0 bal = 0
(13, 13.0) depth = 3 bal = 0
(14, 14.0) depth = 2 bal = 0
(15, 15.0) depth = 3 bal = 0
(16, 16.0) depth = 1 bal = 1
(17, 17.0) depth = 4 bal = 0
(18, 18.0) depth = 3 bal = -1
(19, 19.0) depth = 2 bal = -1
(20, 20.0) depth = 3 bal = 0
----------------------------------------------------------------------
tree size = 20
(1, 1.0)
(2, 2.0)
(3, 3.0)
(4, 4.0)
(5, 5.0)
(6, 6.0)
(7, 7.0)
(8, 8.0)
(9, 9.0)
(10, 10.0)
(11, 11.0)
(12, 12.0)
(13, 13.0)
(14, 14.0)
(15, 15.0)
(16, 16.0)
(17, 17.0)
(18, 18.0)
(19, 19.0)
(20, 20.0)
----------------------------------------------------------------------
(1, "1") depth = 4 bal = 0
(2, "2") depth = 3 bal = 0
(3, "3") depth = 4 bal = 0
(4, "4") depth = 2 bal = -1
(5, "5") depth = 3 bal = 0
(6, "6") depth = 1 bal = 0
(7, "7") depth = 3 bal = 1
(8, "8") depth = 4 bal = 0
(9, "9") depth = 2 bal = 0
(10, "10") depth = 3 bal = 1
(11, "11") depth = 4 bal = 0
(12, "12") depth = 0 bal = 0
(13, "13") depth = 3 bal = 0
(14, "14") depth = 2 bal = 0
(15, "15") depth = 3 bal = 0
(16, "16") depth = 1 bal = 1
(17, "17") depth = 4 bal = 0
(18, "18") depth = 3 bal = -1
(19, "19") depth = 2 bal = -1
(20, "20") depth = 3 bal = 0
----------------------------------------------------------------------
tree size = 20
(1, "1")
(2, "2")
(3, "3")
(4, "4")
(5, "5")
(6, "6")
(7, "7")
(8, "8")
(9, "9")
(10, "10")
(11, "11")
(12, "12")
(13, "13")
(14, "14")
(15, "15")
(16, "16")
(17, "17")
(18, "18")
(19, "19")
(20, "20")
----------------------------------------------------------------------
forwards generator:
(1, "1")
(2, "2")
(3, "3")
(4, "4")
(5, "5")
(6, "6")
(7, "7")
(8, "8")
(9, "9")
(10, "10")
(11, "11")
(12, "12")
(13, "13")
(14, "14")
(15, "15")
(16, "16")
(17, "17")
(18, "18")
(19, "19")
(20, "20")
----------------------------------------------------------------------
backwards generator:
(20, "20")
(19, "19")
(18, "18")
(17, "17")
(16, "16")
(15, "15")
(14, "14")
(13, "13")
(12, "12")
(11, "11")
(10, "10")
(9, "9")
(8, "8")
(7, "7")
(6, "6")
(5, "5")
(4, "4")
(3, "3")
(2, "2")
(1, "1")
----------------------------------------------------------------------</pre>
=={{header|Sidef}}==
{{trans|D}}
<lang ruby>class AVLtree {
has root = nil
struct Node {
Number key,
Number balance = 0,
Node left = nil,
Node right = nil,
Node parent = nil,
}
method insert(key) {
if (root == nil) {
root = Node(key)
return true
}
var n = root
var parent = nil
loop {
if (n.key == key) {
return false
}
parent = n
var goLeft = (n.key > key)
n = (goLeft ? n.left : n.right)
if (n == nil) {
var tn = Node(key, parent: parent)
if (goLeft) {
parent.left = tn
}
else {
parent.right = tn
}
self.rebalance(parent)
break
}
}
return true
}
method delete_key(delKey) {
if (root == nil) { return nil }
var n = root
var parent = root
var delNode = nil
var child = root
while (child != nil) {
parent = n
n = child
child = (delKey >= n.key ? n.right : n.left)
if (delKey == n.key) {
delNode = n
}
}
if (delNode != nil) {
delNode.key = n.key
child = (n.left != nil ? n.left : n.right)
if (root.key == delKey) {
root = child
}
else {
if (parent.left == n) {
parent.left = child
}
else {
parent.right = child
}
self.rebalance(parent)
}
}
}
method rebalance(n) {
if (n == nil) { return nil }
self.setBalance(n)
given (n.balance) {
when (-2) {
if (self.height(n.left.left) >= self.height(n.left.right)) {
n = self.rotate(n, :right)
}
else {
n = self.rotate_twice(n, :left, :right)
}
}
when (2) {
if (self.height(n.right.right) >= self.height(n.right.left)) {
n = self.rotate(n, :left)
}
else {
n = self.rotate_twice(n, :right, :left)
}
}
}
if (n.parent != nil) {
self.rebalance(n.parent)
}
else {
root = n
}
}
method rotate(a, dir) {
var b = (dir == :left ? a.right : a.left)
b.parent = a.parent
(dir == :left) ? (a.right = b.left)
: (a.left = b.right)
if (a.right != nil) {
a.right.parent = a
}
b.$dir = a
a.parent = b
if (b.parent != nil) {
if (b.parent.right == a) {
b.parent.right = b
}
else {
b.parent.left = b
}
}
self.setBalance(a, b)
return b
}
method rotate_twice(n, dir1, dir2) {
n.left = self.rotate(n.left, dir1)
self.rotate(n, dir2)
}
method height(n) {
if (n == nil) { return -1 }
1 + Math.max(self.height(n.left), self.height(n.right))
}
method setBalance(*nodes) {
nodes.each { |n|
n.balance = (self.height(n.right) - self.height(n.left))
}
}
method printBalance {
self.printBalance(root)
}
method printBalance(n) {
if (n != nil) {
self.printBalance(n.left)
print(n.balance, ' ')
self.printBalance(n.right)
}
}
}
var tree = AVLtree()
say "Inserting values 1 to 10"
{|i| tree.insert(i) } << 1..10
print "Printing balance: "
tree.printBalance</lang>
{{out}}
<pre>
Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0
</pre>
=={{header|Sidef}}==
| |||