Дървета, червени и черни дървета

„Здрасти, Амиго!“

„Здравей, Риши!“

„Намерих старите си бележки там и подготвих интересен материал за вас. Мисля, че ще ви е интересно да го чуете.“

„Да го чуем. Винаги намираш нещо интересно, което по-късно се оказва много полезно.“

"ОК. Днес искам да ви разкажа за дърветата , така че ще започна с графики ."

" Графиката е система от точки и прави, които ги свързват. Точките се наричат ​​върхове на графиката, а линиите се наричат ​​ръбове на графиката. Например:"

"Графиката е много удобна за използване като математически модел за различни процеси и задачи от реалния свят. Много различни задачи и алгоритми са измислени за графики, така че те се използват доста често."

„ Например, да предположим, че върховете са градове, а ръбовете са пътища. Тогава търсенето на най-краткия път между градовете става: «при дадена графика намерете най-краткия път между два върха».

„Но пътят от A до B не винаги е същият като пътя от B до A. Така че понякога се предпочитат две различни линии. За да направите това, линиите (ръбовете на графиката) се заменят със стрелки. с други думи, графиката може да има две стрелки: една от A към B и друга от B към A."

"Ако графиката използва стрелки, тогава се нарича насочена графика ; ако има само линии, тогава се нарича неориентирана графика ."

"Всеки връх може да има свой собствен брой ръбове. Един връх също може да няма ниHowви ръбове. Обратно, един връх може да бъде свързан чрез ръбове с всеки друг връх.  Ако всяка двойка върхове в граф е свързана с ребро, тогава нарича се пълна графика. "

„Ако можете да използвате ръбове, за да достигнете до всеки връх в графика, тогава тя се нарича свързана графа. Графа, която има три отделни върха и няма ръбове, все още е графика, но ние я наричаме несвързана графа.“

"За да формирате свързана графа от N върха, имате нужда от поне N-1 ребра. Този тип графика се нарича дърво."

"Освен това, обикновено един връх се избира да бъде корен на дървото , а останалите се обявяват за клонове. Клоните на дървото, които нямат собствени клонове, се наричат ​​листа . Например:"

"Ако всеки елемент от дървото има две деца, тогава се нарича двоично дърво . С други думи, може да има 0 or 2 клона. Можете да видите двоично дърво в горния десен ъгъл."

" Дървото се нарича пълно двоично дърво, когато всеки клон има 2 деца и всички листа (върхове без деца) са на един и същи ред."

"Например:"

"Защо са необходими тези дървета?"

„О, дърветата се използват на много места. Като цяло бинарните дървета са сортирани структурирани данни.“

"Какво е това?"

„Да, много е просто. Ние съхраняваме определена стойност във всеки връх. И всеки елемент следва правило: стойността, съхранена в дясното дете, трябва да бъде по-голяма от стойността, съхранено във върха, а стойността, съхранено в лявото дете, трябва да бъде по-малко от стойността, съхранена във върха.  Това подреждане прави възможно бързото намиране на елементите на дървото, от които се нуждаете."

— Можете ли да поясните Howво означава това?

"Дървовидните елементи обикновено се сортират чрез добавяне. Да предположим, че имаме 7 елемента: 13, 5, 4, 16, 8, 11, 10"

„Ето How се добавят елементите към дървото.“

"Ако търсим числото 7 в това дърво, тогава търсенето ще протече по този начин"

"0) Започнете от корена."

"1a) 7 равно ли е на 13? Не"

"1b) 7 по-голямо ли е от 13? Не, така че преминаваме към лявото поддърво."

"2a) 7 равно ли е на 5? Не."

"2b) 7 по-голямо ли е от 5? Да, така че преминаваме към дясното поддърво."

"3a) 7 равно ли е на 8? Не"

"3b) 7 по-голямо ли е от 8? Не, така че преминаваме към лявото поддърво."

"4a) Няма ляво поддърво, което означава, че числото 7 не е в дървото."

„А. С други думи, трябва само да проверим върховете по пътя от корена до евентуалното местоположение на желаното число. Да, това наистина е бързо.“

„Нещо повече, ако дървото е балансирано, тогава ще трябва да преминете само през около 20 върха, за да търсите мorон елемента.“

"Съгласен съм - не са много."

— Какво имаш предвид под балансирано дърво?

„Дърво, което не е изкривено, т.е. което няма дълги клони. Например, ако елементите вече са бor сортирани, когато сме построor дървото, тогава щяхме да направим много дълго дърво, състоящо се от един клон. “

"Хм. Прав си. И така, Howво да правим?"

„Както вероятно вече се досещате, най-ефективното дърво има клони, които са с приблизително еднаква дължина. Тогава всяко сравнение изхвърля най-голямата част от оставащото поддърво.“

„Така че трябва да възстановим дървото?“

„Да. Трябва да бъде «балансирано» — да бъде възможно най-близко до пълно двоично дърво.»

„За да се реши този проблем, бяха изобретени самобалансиращи се дървета.  Ако дървото се изкриви след добавяне на елемент, то пренарежда елементите леко, за да направи всичко наред.  Ето пример за балансиране:“

„Някои от тези дървета са известни като червено -черни дървета.“

— Защо се наричат ​​червено-черни?

"Техният изобретател начерта всички върхове, използвайки два цвята. Единият цвят беше червен, а другият беше черен. Различните върхове се подчиняват на различни правила. Това формира цялата основа за proceduresата за балансиране."

"Например:"

— И така, Howви са тези правила?

"1) Червен връх не може да бъде дете на червен връх."

"2) Черната дълбочина на всяко листо е една и съща (черната дълбочина се отнася до броя черни върхове по пътя от корена)."

"3) Коренът на дървото е черен."

"Няма да обяснявам How работи това - главата ви вероятно вече експлодира."

"Да. Процесорът ми изпуска малко дим."

„Ето връзка за вас. Ако искате, можете да прочетете повече за това тук.“

Линк към допълнителен материал

— А сега, отидете да си починете.