Crveno-crna stabla

master's thesis

• Author: Barbara Vujičić
• Mentor: Goranka Nogo (mentor)
• Committee member: Goranka Nogo (predsjednik povjerenstva)
• Committee member: Mladen Vuković (član povjerenstva)
• Committee member: Marko Tadić (član povjerenstva)
• Committee member: Dijana Ilišević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2017-02-24, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovom radu prezentirali smo crveno-crno stablo kao vrstu binarnog stabla pretraživanja s dobrom balansiranošću. U prvom poglavlju dali smo osnovnu definiciju crveno-crnog stabla i naveli crveno-crna svojstva koja takvo stablo mora zadovoljavati. Pokazali smo da ta svojstva osiguravaju da nijedan put od korijena do lista nije više od dva puta dulji od bilo kojeg drugog puta od korijena do lista te dokazali da zato takvo stablo s \(n\) čvorova ima visinu \(O(\log {n})\). U sljedećem poglavlju bavili smo se operacijama nad crveno-crnim stablom. Operaciju pretraživanja nismo opisivali jer je jednaka onoj za općenita stabla. Ukratko smo opisali i analizirali trajanje rotacija koje smo, uz mijenjanje boja, najčešće koristili u "popravljanju" crveno-crnog stabla. Veći značaj dali smo operacijama dodavanja i brisanja. Obje operacije baziraju se na istim operacijama definiranim za općenito binarno stablo, ali smo vidjeli da se mogu kršiti svojstva crveno-crnog stabla. Skicama smo prikazali takve slučajeve i kako ih riješiti. Također smo dali pseudokôdove tih operacija i analizirali njihovu vremensku složenost. U zadnjem poglavlju opisali smo projekt Red Black Trees koji je napravljen u sklopu ovog rada i koji implementira rješenje jednog geometrijskog problema uz pomoć crveno-crnog stabla. Objasnili smo kako se pokreće i koristi projekt te dali i opisali dijelove implementacije.

Abstract (english)

In this thesis we have presented the red-black tree as a type of binary search tree with good balance. In the first chapter we have given the definition of red-black trees and listed red-black properties that such tree must satisfy. We have shown that these properties ensure that no path from the root to a leaf is not more than two times longer than any other path from the root to a leaf and proved that therefore such tree with \(n\) nodes has a height of \(O(\log {n})\). In the next chapter we have dealt with the operations of the red-black tree. We have not described search operation because it is similar to that of a general tree. We have described and analyzed the duration of the rotation that has been most often used to "repair" the red-black tree, along with changing colors. We have put more emphasis on insertion and deletion. Both operations are based on the same operations defined for generally binary tree, but we have seen that they can violate the properties of red-black tree. We have presented these cases with sketches and described how to solve them. We have also given pseudocode for these operations and analyzed their time complexity. In the last chapter we have described the project Red Black Trees that was made as part of this work and that implements the solution of one geometric problem with red-black tree. We have explained how to run and use the project, and we have given and described parts of implementation.

• Keywords: crveno-crno stablo; binarno pretraživanje; operacije nad crveno-crnim stablom
• Keywords (english): red-black tree; binary search; operations of the red-black tree
• Language: croatian
• URN:NBN: urn:nbn:hr:217:707353
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2017-04-28 11:30:25