– Szia Amigo!
– Szia, Rishi!
"Ott találtam a régi jegyzeteimet, és készítettem egy érdekes anyagot a számodra. Azt hiszem, érdekelni fogod."
"Halljuk. Mindig találsz valami érdekeset, ami később nagyon hasznosnak bizonyul."
"Rendben. Ma a fákról szeretnék mesélni neked , ezért grafikonokkal kezdem ."
" A gráf pontok és azokat összekötő vonalak rendszere. A pontokat a gráf csúcsainak, a vonalakat pedig a gráf éleinek nevezzük. Például:"
"A gráf nagyon kényelmesen használható matematikai modellként különféle valós folyamatokhoz és feladatokhoz. A gráfokhoz sokféle feladatot és algoritmust találtak ki, így elég gyakran használják őket."
" Például tegyük fel, hogy a csúcsok városok, az élek pedig utak. Ekkor a városok közötti legrövidebb út keresése a következő lesz: «adva egy gráfot, keresse meg a legrövidebb utat két csúcs között».
"De az A-ból B-be vezető út nem mindig ugyanaz, mint a B-ből A-ba vezető út. Tehát néha két különböző vonalat érdemes használni. Ehhez a vonalakat (a grafikon éleit) nyilakkal helyettesítjük. Más szóval, a grafikonon két nyíl lehet: egy A-tól B-ig, egy másik pedig B-től A-ig."
"Ha a gráf nyilakat használ, akkor irányított gráfnak nevezzük , ha csak vonalakat tartalmaz, akkor irányítatlan gráfnak . "
"Minden csúcsnak megvan a maga számú éle. Egy csúcsnak lehet egyáltalán éle sem. Ezzel szemben egy csúcs összeköthető élekkel minden másik csúcshoz. Ha a gráfban minden csúcspárt egy él köt össze, akkor ezt teljes gráfnak hívják. "
"Ha egy gráf minden csúcsát elérheti élekkel, akkor azt összekapcsolt gráfnak nevezzük. Az a gráf, amelynek három különálló csúcsa van, és nincs él, továbbra is gráf, de mi szétkapcsolt gráfnak nevezzük ."
"Ahhoz, hogy N csúcsból összefüggő gráfot alkossunk, legalább N-1 élre van szükség. Az ilyen típusú gráfokat fának nevezzük."
"Sőt, általában egy csúcsot választanak ki a fa gyökerének , a többit pedig ágnak nyilvánítják. Azokat a faágakat, amelyeknek nincs saját ága, leveleknek nevezik . Például:"
"Ha a fa minden elemének két gyermeke van, akkor azt bináris fának nevezik . Más szóval, lehet 0 vagy 2 ág. A jobb felső sarokban egy bináris fa látható ."
" Egy fát teljes bináris fának nevezünk, ha minden ágnak 2 gyermeke van, és az összes levél (gyermek nélküli csúcs) ugyanabban a sorban van."
"Például:"
– Miért van szükség ezekre a fákra?
"Ó, a fákat sok helyen használják. Általában a bináris fák rendezett strukturált adatok."
"Mi az?"
"Igen, ez nagyon egyszerű. Minden csúcsban tárolunk egy bizonyos értéket. És minden elem egy szabályt követ: a jobb oldali gyermekben tárolt értéknek nagyobbnak kell lennie, mint a csúcsban tárolt értéknek, és a bal oldali gyermekben tárolt értéknek kell lennie. kisebb legyen, mint a csúcsban tárolt érték. Ez a rendezés lehetővé teszi a fa szükséges elemeinek gyors megtalálását."
– Tisztáznád, hogy ez mit jelent?
"A fa elemeket általában összeadással rendezik. Tegyük fel, hogy 7 elemünk van: 13, 5, 4, 16, 8, 11, 10"
"Íme, hogyan adják hozzá az elemeket a fához."
"Ha a 7-es számot keressük ebben a fában, akkor a keresés így fog menni"
"0) Kezdje a gyökérnél."
"1a) 7 egyenlő 13-mal? Nem"
"1b) 7 nagyobb, mint 13? Nem, tehát a bal oldali részfára lépünk."
"2a) 7 egyenlő 5-tel? Nem."
"2b) A 7 nagyobb, mint 5? Igen, tehát a jobb oldali részfára lépünk."
"3a) 7 egyenlő 8-cal? Nem"
"3b) A 7 nagyobb, mint a 8? Nem, tehát a bal oldali részfára lépünk."
"4a) Nincs bal oldali részfa, ami azt jelenti, hogy a 7-es szám nincs a fában."
"Ah. Más szóval, csak a gyökértől a kívánt szám lehetséges helyéig tartó útvonal csúcsait kell ellenőriznünk. Igen, ez tényleg gyors."
"Mi több, ha a fa kiegyensúlyozott, akkor csak körülbelül 20 csúcson kell áthaladnia millió elem kereséséhez."
– Egyetértek – ez nem sok.
– Mit értesz kiegyensúlyozott fa alatt?
"Egy olyan fa, ami nem torz, azaz nincs hosszú ága. Például, ha az elemek már a fa építésekor rendezve voltak, akkor egy nagyon hosszú, egy ágból álló fát készítettünk volna. "
"Hmm. Igazad van. Szóval mit tegyünk?"
"Amint azt valószínűleg már kitalálta, a leghatékonyabb fának körülbelül azonos hosszúságú ágai vannak. Ezután minden összehasonlítás eldobja a fennmaradó részfa legnagyobb részét."
– Tehát újjá kell építeni a fát?
"Igen. Kiegyensúlyozottnak kell lennie - hogy a lehető legközelebb legyen egy teljes bináris fához."
"A probléma megoldására önkiegyensúlyozó fákat találtak ki. Ha a fa egy elem hozzáadása után eltorzul, akkor kissé átrendezi az elemeket, hogy minden rendben legyen. Íme egy példa az egyensúlyozásra:
"E fák némelyikét vörös -fekete fának nevezik ."
– Miért hívják piros-feketének?
"Feltalálójuk két színnel rajzolta meg az összes csúcsot. Az egyik szín piros, a másik fekete volt. A különböző csúcsok különböző szabályoknak engedelmeskednek. Ez képezi a kiegyensúlyozási eljárás teljes alapját."
"Például:"
– Szóval mik ezek a szabályok?
"1) A vörös csúcs nem lehet a piros csúcs gyermeke."
"2) Minden levél fekete mélysége azonos (a fekete mélység a gyökértől induló úton lévő fekete csúcsok számát jelenti)."
"3) A fa gyökere fekete."
– Nem magyarázom el, hogyan működik ez – valószínűleg már felrobban a fejed.
– Igen. A processzorom egy kis füstöt bocsát ki.
"Itt van egy link az ön számára. Ha akarja, itt olvashat róla többet."
– És most menj egy kis szünetet.
GO TO FULL VERSION