Wikiszótár

Day-Stout-Warren-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈdɒiʃtoutvɒrːɛnɒlɡoritmuʃ]

Főnév

Day-Stout-Warren-algoritmus

  1. (matematika)

Day-Stout-Warren (DSW) algoritmus

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á.


Motiváció

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:

  1. Nem igényel extra memóriát (in-place kiegyensúlyozás),
  2. Kiegyensúlyozásának időbonyolultsága ( O(n) ).


Működési elv

A DSW algoritmus két fő lépésből áll:

  1. “Fa-vonal” alakzat létrehozása (Tree-to-Vine):
    • A bináris keresőfát egy “láncszerű” struktúrává alakítjuk úgy, hogy minden csomópontnak csak a jobb gyereke legyen.
    • Ez történeti sorrendben átalakítja a fát egy sorozatosan jobbra hajló “vonal”-fává.
  2. Kiegyensúlyozott fa létrehozása (Vine-to-Tree):
    • A láncszerű szerkezetet újra strukturáljuk úgy, hogy az egy teljesen kiegyensúlyozott bináris keresőfát eredményezzen.
    • Ehhez forgatásokat alkalmazunk, hogy a csomópontokat a megfelelő szintekre helyezzük.


Lépések részletezése

1. Fa-vonal alakzat létrehozása (Tree-to-Vine)

  • Bal gyermekek folyamatos eltávolítása jobb oldali elforgatásokkal.
  • Minden bal gyermek felfelé kerül a jobb oldalra.

2. Kiegyensúlyozott fa létrehozása (Vine-to-Tree)

  • A láncszerű fát bal oldali elforgatásokkal alakítjuk vissza kiegyensúlyozott bináris keresőfává.
  • A forgatásokat úgy végezzük el, hogy a fa minél teljesebb legyen (a lehető legjobban kitöltött fa).


Algoritmus implementációja

Python Implementáció

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)

Kimenet

Eredeti fa (inorder):
3 5 7 10 15 20 25 
Kiegyensúlyozott fa (inorder):
3 5 7 10 15 20 25

Algoritmus idő- és tárbonyolultsága

  1. Időbonyolultság: ( O(n) ), ahol ( n ) a fa csomópontjainak száma.
  2. Tárbonyolultság: ( O(1) ), mert a fa in-place kerül átalakításra (nem használ további memóriát).


Összefoglalás

  1. Day-Stout-Warren algoritmus célja: A bináris keresőfa kiegyensúlyozása.
  2. Fő lépések:
    • Tree-to-Vine: A fát láncszerűvé alakítja.
    • Vine-to-Tree: A láncszerű fából kiegyensúlyozott fát épít.
  3. Előnyök:
    • Egyszerű és hatékony ( O(n) )-es időbonyolultsággal.
    • In-place működik, nem igényel extra memóriát.
  4. Alkalmazás: Olyan esetekben használható, ahol egy bináris keresőfát utólag kell kiegyensúlyozni.

Ez az algoritmus hatékony alternatíva az AVL- vagy piros-fekete fák folyamatos kiegyensúlyozásához.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Day-Stout-Warren-algoritmus&oldid=3480707”