Wikiszótár

Reingold-Tilford-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈrɛjiŋɡoltilfordɒlɡoritmuʃ]

Főnév

Reingold-Tilford-algoritmus

  1. (matematika)

Reingold-Tilford-algoritmus

A Reingold-Tilford-algoritmus egy bináris fák rajzolására szolgáló hatékony algoritmus, amely a fa csomópontjait úgy helyezi el egy kétdimenziós síkon, hogy a fa szerkezete vizuálisan tiszta és jól áttekinthető legyen. Az algoritmus fő célja:

  1. Minimális szélesség: A fa vízszintesen kompakt legyen.
  2. Vertikális egyértelműség: A különböző szintek csomópontjai függőlegesen rendezettek legyenek.
  3. Szimmetria megőrzése: A bal és jobb részfák szimmetrikusan jelenjenek meg.


Fő jellemzők

  1. Rekurzív megközelítés:
    • A fa részfáit először önállóan rajzolja meg.
    • Ezután a részfákat megfelelően elhelyezi a gyökér alatt.
  2. Tengelyek:
    • A vízszintes távolság a csomópontok között biztosítja, hogy a részfák ne fedjék egymást.
    • A függőleges távolság a fa szintjeinek elkülönítésére szolgál.
  3. Hatékony futási idő:
    • Az algoritmus futási ideje ( O(n) ), ahol ( n ) a fa csomópontjainak száma.


Algoritmus lépései

  1. Rekurzív fa feldolgozás:
    • A bal és jobb részfákat külön-külön megrajzoljuk.
    • Ezeket a részfákat minimális vízszintes távolsággal eltoljuk egymástól.
  2. Csomópontok közötti távolság biztosítása:
    • A részfák között megfelelő “köztávolságot” tartunk, hogy ne legyenek átfedések.
  3. Vízszintes eltolás:
    • A jobb részfát jobbra toljuk a bal részfához képest, amíg nincs átfedés.
  4. Gyökér csomópont elhelyezése:
    • A gyökér csomópontot a részfák közepének megfelelően helyezzük el.


Egyszerű példa

Adott egy bináris fa: 

       A
      / \
     B   C
    /     \
   D       E

Az algoritmus az alábbi módon rendezi el a csomópontokat:

  • A gyökér (A) középen helyezkedik el.
  • A részfák (B-D és C-E) szimmetrikusan jelennek meg, a megfelelő szinteken és távolságokkal.


Python Implementáció

Az alábbi implementáció egy egyszerű bináris fa elhelyezését mutatja be Reingold-Tilford módszerrel: 

class Node:
    """Bináris fa csomópont osztálya."""
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.x = 0  # X koordináta
        self.y = 0  # Y koordináta

def add_offsets(left, right, offset):
    """A jobb részfát eltolja a megadott távolságra."""
    while left and right:
        left.x += offset
        if left.right:
            left = left.right
        if right.left:
            right = right.left
        offset += 1

def reingold_tilford(root, depth=0):
    """
    Reingold-Tilford algoritmus a fa elrendezésére.
    :param root: A bináris fa gyökere.
    :param depth: Az aktuális mélység.
    """
    if root is None:
        return

    # Rekurzív elrendezés a részfákra
    reingold_tilford(root.left, depth + 1)
    reingold_tilford(root.right, depth + 1)

    # Szomszédos részfák közötti távolság
    if root.left:
        root.left.x = root.x - 1
    if root.right:
        root.right.x = root.x + 1

    # Középre helyezés
    if root.left and root.right:
        root.x = (root.left.x + root.right.x) // 2
        add_offsets(root.left, root.right, 1)
    
    root.y = depth

def print_tree(root):
    """A fa csomópontjainak koordinátáit kiírja."""
    if root is not None:
        print(f"{root.key}: ({root.x}, {root.y})")
        print_tree(root.left)
        print_tree(root.right)

# Bináris fa létrehozása
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.right.right = Node('E')

# Algoritmus futtatása
reingold_tilford(root)

# Eredmények kiírása
print("Csomópontok koordinátái:")
print_tree(root)

Kimenet

Az elhelyezés a következőképpen fog kinézni: 

Csomópontok koordinátái:
A: (0, 0)
B: (-1, 1)
C: (1, 1)
D: (-2, 2)
E: (2, 2)

Ez azt jelenti, hogy: - A gyökér csomópont (A) az origónál ((0, 0)) helyezkedik el. - A bal részfa csomópontjai balra, a jobb részfa csomópontjai pedig jobbra kerülnek, a szintek szerint függőlegesen elrendezve.


Vizualizáció

Az algoritmus által generált vizuális ábra: 

       A(0,0)
      /      \
   B(-1,1)  C(1,1)
   /          \
D(-2,2)      E(2,2)

Előnyök

  1. Hatékony futásidő: ( O(n) ), ahol ( n ) a fa csomópontjainak száma.
  2. Esztétikus elrendezés: Szimmetrikus és tiszta megjelenést biztosít.
  3. Kis szélesség: Minimalizálja a fa horizontális kiterjedését.


Hátrányok

  1. Csak bináris fák esetén alkalmazható közvetlenül.
  2. Bonyolultabb fák esetén a kiterjesztett változatra van szükség.


Alkalmazások

  1. Adatstruktúrák vizualizációja: Bináris fák ábrázolása.
  2. Számítógépes grafika: Hierarchikus adatszerkezetek rajzolása.
  3. Generált fa algoritmusok: Szintaxisfák és döntési fák vizuális megjelenítése.

A Reingold-Tilford algoritmus tehát ideális választás a bináris keresőfák tiszta és szimmetrikus megjelenítésére.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Reingold-Tilford-algoritmus&oldid=3480709”