148 lines
4.1 KiB
Plaintext
148 lines
4.1 KiB
Plaintext
// AVL-Tree C code, https://www.programiz.com/dsa/avl-tree
|
|
// Ported to Yabasic by Galileo 2022/07
|
|
|
|
KEY = 1 : LRIGHT = 2 : LLEFT = 3 : HEIGHT = 4
|
|
|
|
root = 0 : ramas = 5 : indice = 0
|
|
|
|
dim arbol(ramas, 4)
|
|
|
|
|
|
sub rotateRight(y)
|
|
local x, T2
|
|
|
|
x = arbol(y, LLEFT)
|
|
T2 = arbol(x, LRIGHT)
|
|
arbol(x, LRIGHT) = y
|
|
arbol(y, LLEFT) = T2
|
|
arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
|
|
arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
|
|
return x
|
|
end sub
|
|
|
|
|
|
sub rotateLeft(x)
|
|
local y, T2
|
|
|
|
y = arbol(x, LRIGHT)
|
|
T2 = arbol(y, LLEFT)
|
|
arbol(y, LLEFT) = x
|
|
arbol(x, LRIGHT) = T2
|
|
arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
|
|
arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
|
|
return y
|
|
end sub
|
|
|
|
|
|
sub Balance(current)
|
|
return height(arbol(current, LLEFT)) - height(arbol(current, LRIGHT))
|
|
end sub
|
|
|
|
|
|
sub height(current)
|
|
return arbol(current, HEIGHT)
|
|
end sub
|
|
|
|
|
|
sub insert(current, key)
|
|
local balance
|
|
|
|
if current = 0 indice = indice + 1 : if indice > ramas then ramas = ramas + 5 : redim arbol(ramas, 4) endif : arbol(indice, KEY) = key : arbol(indice, HEIGHT) = 1 : return indice
|
|
if key < arbol(current, KEY) then
|
|
arbol(current, LLEFT) = insert(arbol(current, LLEFT), key)
|
|
elsif key > arbol(current, KEY) then
|
|
arbol(current, LRIGHT) = insert(arbol(current, LRIGHT), key)
|
|
else
|
|
return current
|
|
endif
|
|
|
|
arbol(current, HEIGHT) = max(height(arbol(current, LLEFT)), height(arbol(current, LRIGHT))) + 1
|
|
balance = Balance(current)
|
|
if balance > 1 and key < arbol(arbol(current, LLEFT), KEY) return rotateRight(current)
|
|
if balance < -1 and key > arbol(arbol(current, LRIGHT), KEY) return rotateLeft(current)
|
|
if balance > 1 and key > arbol(arbol(current, LLEFT), KEY) then
|
|
arbol(current, LLEFT) = rotateLeft(arbol(current, LLEFT))
|
|
return rotateRight(current)
|
|
endif
|
|
if balance < -1 and key < arbol(arbol(current, LRIGHT), KEY) then
|
|
arbol(current, LRIGHT) = rotateRight(arbol(current, LRIGHT))
|
|
return rotateLeft(current)
|
|
endif
|
|
return current
|
|
end sub
|
|
|
|
|
|
sub minValueNode(current)
|
|
while arbol(current, LLEFT)
|
|
current = arbol(current, LLEFT)
|
|
wend
|
|
|
|
return current
|
|
end sub
|
|
|
|
// Delete a nodes
|
|
sub deleteNode(root, key)
|
|
local temp, balance
|
|
// Find the node and delete it
|
|
if root = 0 return root
|
|
|
|
if key < arbol(root, KEY) then
|
|
arbol(root, LLEFT) = deleteNode(arbol(root, LLEFT), key)
|
|
elsif key > arbol(root, KEY) then
|
|
arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), key)
|
|
else
|
|
if arbol(root, LLEFT) = 0 or arbol(root, LRIGHT) = 0 then
|
|
temp = max(arbol(root, LLEFT), arbol(root, LRIGHT))
|
|
|
|
if temp = 0 then
|
|
temp = root
|
|
root = 0
|
|
else
|
|
root = temp
|
|
endif
|
|
else
|
|
temp = minValueNode(arbol(root, LRIGHT))
|
|
arbol(root, KEY) = arbol(temp, KEY)
|
|
arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), arbol(temp, KEY))
|
|
endif
|
|
endif
|
|
|
|
if root = 0 return root
|
|
|
|
// Update the balance factor of each node and
|
|
// balance the tree
|
|
arbol(root, HEIGHT) = 1 + max(height(arbol(root, LLEFT)), height(arbol(root, LRIGHT)))
|
|
|
|
balance = Balance(root)
|
|
if balance > 1 and Balance(arbol(root, LLEFT)) >= 0 return rightRotate(root)
|
|
if balance > 1 and Balance(arbol(root, LLEFT)) < 0 arbol(root, LLEFT) = leftRotate(arbol(root, LLEFT)) : return rightRotate(root)
|
|
if balance < -1 and Balance(arbol(root, LRIGHT)) <= 0 return leftRotate(root)
|
|
if balance < -1 and Balance(arbol(root, LRIGHT)) > 0 arbol(root, LRIGHT) = rightRotate(arbol(root, LRIGHT)) : return leftRotate(root)
|
|
|
|
return root
|
|
end sub
|
|
|
|
sub preOrder(temp)
|
|
if temp then
|
|
print arbol(temp, KEY), " ", arbol(temp, HEIGHT), " ", Balance(temp)
|
|
preOrder(arbol(temp, LLEFT))
|
|
preOrder(arbol(temp, LRIGHT))
|
|
endif
|
|
end sub
|
|
|
|
|
|
root = insert(root, 2)
|
|
root = insert(root, 1)
|
|
root = insert(root, 7)
|
|
root = insert(root, 4)
|
|
root = insert(root, 5)
|
|
root = insert(root, 3)
|
|
root = insert(root, 8)
|
|
|
|
preOrder(root)
|
|
|
|
root = deleteNode(root, 3)
|
|
|
|
print "\nAfter deletion: "
|
|
preOrder(root)
|