A Day-Stout-Warren (DSW) algoritmus egy hatékony módszer bináris keresőfák kiegyensúlyozására. Az algoritmust Colin Day és John Stout fejlesztette ki 1979-ben, és célja, hogy egy tetszőleges bináris keresőfát (BST) alakítson át egy kiegyensúlyozott bináris keresőfává.
Egy kiegyensúlyozatlan bináris keresőfa legrosszabb esetben lineáris szerkezetűvé válhat (például ha a fa lényegében egy láncot alkot). Ebben az esetben az alapműveletek – keresés, beszúrás, törlés – időbonyolultsága ( O(n) ) lehet, ahol ( n ) a csomópontok száma. Egy kiegyensúlyozott bináris keresőfában ezek az időbonyolultságok ( O(n) )-re csökkennek.
A DSW algoritmus előnye, hogy:
A DSW algoritmus két fő lépésből áll:
class Node:
"""Bináris fa csomópont osztálya."""
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def right_rotate(grandparent, parent):
"""Jobb oldali forgatás."""
temp = parent.left
parent.left = temp.right
temp.right = parent
grandparent.right = temp
def left_rotate(grandparent, parent):
"""Bal oldali forgatás."""
temp = parent.right
parent.right = temp.left
temp.left = parent
grandparent.right = temp
def tree_to_vine(root):
"""A bináris keresőfát láncszerűvé alakítja (Tree-to-Vine)."""
grandparent = Node(None)
grandparent.right = root
tail = grandparent
rest = tail.right
while rest:
if rest.left:
right_rotate(tail, rest)
rest = tail.right
else:
tail = rest
rest = rest.right
return grandparent.right
def vine_to_tree(root, size):
"""A láncszerű fát kiegyensúlyozott fává alakítja (Vine-to-Tree)."""
grandparent = Node(None)
grandparent.right = root
m = 2 ** (size.bit_length() - 1) - 1 # Teljes fa mérete
make_rotations(grandparent, size - m)
while m > 1:
m //= 2
make_rotations(grandparent, m)
return grandparent.right
def make_rotations(grandparent, count):
"""Segédfüggvény a forgatások elvégzéséhez."""
parent = grandparent.right
for _ in range(count):
if parent.right:
left_rotate(grandparent, parent)
parent = grandparent.right
grandparent = parent
parent = parent.right
def dsw_balance_tree(root):
"""A teljes DSW algoritmus."""
# Tree-to-Vine lépés
size = count_nodes(root)
root = tree_to_vine(root)
# Vine-to-Tree lépés
root = vine_to_tree(root, size)
return root
def count_nodes(node):
"""Rekurzívan megszámolja a fa csomópontjait."""
if not node:
return 0
return 1 + count_nodes(node.left) + count_nodes(node.right)
def inorder_traversal(node):
"""Bejárja a fát inorder sorrendben."""
if node:
inorder_traversal(node.left)
print(node.key, end=" ")
inorder_traversal(node.right)
# Példa használat
root = Node(10)
root.left = Node(5)
root.right = Node(20)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.left = Node(15)
root.right.right = Node(25)
print("Eredeti fa (inorder):")
inorder_traversal(root)
print()
# DSW kiegyensúlyozás
balanced_root = dsw_balance_tree(root)
print("Kiegyensúlyozott fa (inorder):")
inorder_traversal(balanced_root)
Eredeti fa (inorder): 3 5 7 10 15 20 25 Kiegyensúlyozott fa (inorder): 3 5 7 10 15 20 25
Ez az algoritmus hatékony alternatíva az AVL- vagy piros-fekete fák folyamatos kiegyensúlyozásához.