AVL ve Kırmızı Siyah Ağaçlar

1. GİRİŞ

AVL ve Kırmızı-Siyah Ağaçlar (Red-Black Tree) literatürde fazlaca kullanılan ikili arama ağaçlarıdır. Bu ağaçların sağladığı avantajların daha iyi kavranabilmesi adına, öncelikle ikili arama ağaçlarının (Binary Search Tree) denge problemi üzerine durulmalıdır. İkili arama ağaçları, bilgisayar bilimlerindeki pek uygulama için oldukça verimlidir. Buna karşın en kötü durum performansı düşüktür [1]. Çünkü bir ikili arama ağacının performansı büyük ölçüde şekline bağlıdır ve en kötü durumda, zaman karmaşıklığı O(n) olan doğrusal bir yapıya dönüşebilir.

İkili arama ağaçlarının yapısına bakıldığında en kötü durumun çalışma süresinin ağacın yüksekliği (h) ile doğru orantılı olduğu görülür [2]. Ağaç yapılarında her bir seviye karmaşıklığa etki eden yegâne unsurdur. Buna bağlı olarak, derinlik arttıkça işlem karmaşıklığı da artar. Bu sebeple, ikili arama ağaçlarının dengeli (Şekil 1.1.) olması istenir. Bir ağacın dengeli olabilmesi için, herhangi bir düğümüne bağlı olan alt ağaçların yükseklikleri arasındaki fark en fazla bir olmalıdır [3]. Bahsedilen AVL ve kırmızı-siyah ağaçları ikili arama ağaçlarının işlem karmaşıklığını azaltmak yani dengelemek amacıyla tercih edilen yöntemlerdir.

2. KIRMIZI-SİYAH AĞAÇLAR

Kırmızı-siyah ağaçlar en kötü durumda dahi arama, ekleme ve silme işlemlerin garantili olarak O(log(n)) zamanında çalışmasına olanak sağlayan dengeli arama ağaçlarından biridir [4]. Bu dengeli yapı, veri dağılımından bağımsız olarak tutarlı performans sağlayarak, verimliliğin ve öngörülebilirliğin çok önemli olduğu senaryolarda Kırmızı-siyah ağaçları değerli kılar. Kırmızı-siyah ağaçları [5–6] her düğümde fazladan bir bit saklayabilen, yarı dengeli ikili arama ağaçlarıdır. Bahsedilen bitler, bulunduğu düğümün rengini (kırmızı yahut siyah) belirten değişkenlerdir. Bu veri yapısında, kökten yapraklara kadar olan yolların hiçbiri diğerinden iki fazla düğüm içeremez. Bu durum, kırmızı-siyah ağaçların diğer ikili ağaçlara göre daha dengeli olmasını sağlar [7].

Kırmızı-Siyah Ağaçların ardındaki ana fikir, ağacın yapısına ek kısıtlamalar getirerek ekleme ve silme işlemlerinden sonra bile dengede kalmasını sağlamaktır [8]. Bu denge, her bir düğüme renkler (kırmızı veya siyah) atanarak ve bir dizi özellik uygulanarak sağlanır.

Bir ikili ağacın kırmızı-siyah ağaç veri yapısında olabilmesi için birtakım koşulları karşılaması beklenir. Bu koşullar şu şekildedir;

a. Her düğüm kırmızı ya da siyah olmalıdır.

b. Kök daima siyah olmalıdır.

c. Her yaprak siyah olmalıdır.

d. Düğüm kırmızı ise her iki çocuğu da siyah olmalıdır.

e. Her düğüm için, o düğümün soyundan gelen ve yapraklara kadar ilerleyen tüm basit yollardaki siyah düğüm sayısı eşit olmalıdır [9].

İçerisinde n düğüm bulunduran kırmızı-siyah ağacın yüksekliği en fazla 2log(n+1) olacağı için kırmızı-siyah ağaçların iyi bir arama aracı olduğu söylenebilir [10].

2.1 KIRMIZI — SİYAH AĞAÇLARDA YAPILAN İŞLEMLER

Kırmızı-Siyah ağacında dengelemeyi yapmak için iki araç kullanılır [11].

• Yeniden renklendirme
• Döndürme [Sola Döndürme (Şekil 2.1.2.) — Sağa Döndürme (Şekil 2.1.3.)]

Yeniden renklendirme, düğüm renginin değiştirilmesi işlemidir. Düğüm kırmızı ise siyah, siyah ise kırmızı olur. NIL (ya da NULL) düğümünün her zaman siyah renkte olduğu unutulmamalıdır. Bununla birlikte bu iki aracın kullanımına önce yeniden renklendirme ile başlanmakla birlikte, yeniden renklendirmenin işe yaramadığı durumlarda döndürme işlemine başvurulur. Döndürme işlemi sola (Şekil 2.2.) ve sağa (Şekil 2.3.) olacak şekilde iki şekilde gerçekleştirilir.

2.2 ZAMAN VE ALAN KARMAŞIKLIKLARI

Kırmızı-Siyah Ağaçların zaman ve alan karmaşıklığı analizini özetleyen şema aşağıda (Tablo 2.2.1.) verilmiştir. Bu tabloda görüldüğü üzere, işlemin ne olduğu fark etmeksizin zaman karmaşıklığı O(log(n)) ve giriş boyutundan bağımsız olarak her işlem için alan karmaşıklığı O(1) olarak kabul edilir. Bununla birlikte, bir bütün olarak Kırmızı-Siyah Ağacın alan karmaşıklığı, ağaçtaki düğüm sayısı (n) ile doğrusal olarak büyüdüğü için O(n)’dir.

2.3 KIRMIZI — SİYAH AĞAÇLAR NEDEN TERCİH EDİLİR?

Kırmızı-Siyah Ağaçlar, dengeli yapıları ve verimli çalışmaları nedeniyle pek çok alanda yaygın olarak kullanılmaktadır. Bu sebeplerden bazıları şunlardır.

Dengeli Yapı: Kırmızı-Siyah Ağaçlar, ağacın yüksekliğinin düğüm sayısına göre logaritmik kalmasını sağlayarak dengeli bir yapı sağlar. Bu denge, önemli işlemler için O(log(n))’nin en kötü durum zaman karmaşıklığını garanti ederek verimli arama, ekleme ve silme işlemlerini mümkün kılar [7].

Performans Garantisi: Yukarıdaki tabloda (Tablo 2.1) da gösterildiği üzere bu veri yapısı işlem ne olursa olsun en kötü senaryonun ne olduğu bilinir. Bu özellik ile birlikte gelen öngörülebilirlik ve verimlilik, kırmızı-siyah ağaç yapısını hızlı, güvenilir veri depolama ve geri alma gerektiren uygulamalar için uygun hale getirir [12]

Çok yönlülük: Kırmızı-Siyah Ağaçlar çok çeşitli uygulamalarda kullanılabilir. Genellikle veri tabanı indekslemede, sembol tablolarında, dosya sistemlerinde, aralık ağaçlarında, önbelleğe alma mekanizmalarında, ağ yönlendirmede ve daha fazlasında kullanılırlar [13–20].

Alan Verimliliği: Kırmızı-Siyah Ağaçlar, nispeten verimli bir alan karmaşıklığı olan O(n)’ye sahiptir. Bahsedilen “n”, ağaçtaki düğümlerin sayısını temsil eder. Bu, kırmızı-siyah ağaç veri yapısını bellek kullanımının optimize edilmesi gereken senaryolar için uygun hale getirir [7].

Sadelik: Kırmızı-Siyah Ağaçlar, AVL Ağaçları gibi diğer bazı kendi kendini dengeleyen ağaç yapılarına kıyasla daha basit bir uygulama sunmaktadır. Yeniden dengeleme işlemleri sırasında daha az rotasyon gerektirirler, bu da uygulama sürecini basitleştirmektedir [21].

Dokümantasyon: Kırmızı-Siyah Ağaçlar kapsamlı bir şekilde araştırılmış ve belgelenmiştir. Bunun bir sonucu olarak, onları anlamak ve kullanmak için çok sayıda bilgi ve kaynak mevcuttur. Kırmızı-Siyah Ağaçların algoritmalarını, analizlerini ve açıklamalarını içeren çeşitli ders kitapları, araştırma makaleleri ve makaleler vardır [20][22–23].

2.4 KIRMIZI — SİYAH AĞAÇLARIN KULLANIM ALANLARI

Veri Tabanı Sistemleri: Veri tabanı sistemlerinde verileri indekslemek ve düzenlemek için yaygın olarak kullanılır. Verimli arama, ekleme ve silme işlemlerini etkinleştirir ve verilere erişirken ve verileri işlerken optimum performans sağlar [7].

Sembol Tabloları: Kırmızı-siyah ağaçlar, sembolleri ve bunlarla ilgili bilgileri depolamak için derleyiciler, yorumlayıcılar ve programlama dili uygulamaları tarafından yaygın olarak kullanılır. Bu, verimli sembol arama ve yönetimini mümkün kılarak derleme ve yorumlamayı hızlandırır [12].

Dosya sistemi: Dosyaları isme veya diğer niteliklere göre düzenlemek ve almak için bir dosya sisteminde bir Kırmızı-Siyah Ağaç uygulanabilir. Bu, dosya işlemlerinin genel performansını artırır ve verimli dosya yönetimini ve erişimi kolaylaştırır [3].

Aralık Ağaçları (Interval Trees): Kırmızı-siyah ağaçlar, aralık ağaçlarını uygulamak için hesaplamalı geometri algoritmalarında kullanılır. Aralık ağaçları, kapsamların veya örtüşen kapsamların verimli bir şekilde ele alınmasına olanak tanır ve zamanlama, olay yönetimi ve kaynak tahsisi gibi uygulamalar için kullanışlıdır [8].

Önbelleğe Alma Mekanizmaları: Genellikle en sık erişilen veya en son kullanılan öğelerin depolandığı önbelleğe alma mekanizmalarında kullanılır. Kendi kendini dengeleme özelliği, önbelleğe alınan öğelerin verimli bir şekilde kaldırılmasını ve değiştirilmesini sağlayarak daha iyi önbellek performansı sağlar [23].

Ağ Yönlendirme: Verimli yönlendirme tablolarını korumak için ağ yönlendirme algoritmalarında uygulanabilir. Bilgisayar ağları üzerinden hızlı ve optimum paket iletimi sağlayarak verimli veri iletimi ve ağ performansı sağlar [19].

Dil Kitaplıkları ve Çerçeveleri: C++ Standart Şablon Kitaplığı (STL) seti ve harita uygulamaları gibi çeşitli dil kitaplıklarında ve çerçevelerinde kullanılır. Çok çeşitli uygulamalarda verileri depolamak ve işlemek için verimli veri yapıları sağlar [25].

3. AVL AĞAÇLARI

AVL ağacı, mucitleri Adelson-Velsky ve Landis’in adını taşıyan ve “yükseklik dengeli” olarak tanımlanan ikili arama ağaçlarıdır. Bu ağaçlar, herhangi bir düğümün sağ ve sol alt ağaçlarının yükseklikleri farkının en fazla bir olmasını sağlayarak ağaç yapısını dengeli hale getirir. Başka bir deyişle, katı bir dengeleme koşulu uygulayarak onu en dengeli ikili arama ağacı yapılarından biri yapmaktadır.

3.1 DENGE FAKTÖRÜ

AVL ağacındaki her düğüm, sağ alt ağacın yüksekliği eksi sol alt ağacın yüksekliği olan bir denge faktörü tutar. Ağacı dengede tutmak için denge faktörü -1, 0 veya 1 olabilir.

“ Denge faktörü = Yükseklik(Sol Alt Ağaç) — Yükseklik(Sağ Alt Ağaç) ”

Bu denge faktörü özelliği, AVL Ağaçlarının eklemeler ve silmeler sırasında yapılarını verimli bir şekilde ayarlamasını sağlar [18]. AVL ağaçları, her düğümün sol ve sağ alt ağaçları arasındaki yükseklik farkının en fazla bir olmasını sağlayan yükseklik dengeleme özelliğine bağlıdır. Bu özellik, ağaç stabilitesini korur, aşırı bozulmayı önler ve verimli arama, ekleme ve silme işlemlerine olanak tanır [7].

3.2 DENGESİZLİK DURUMLARI

Giriş kısmında da belirtildiği üzere, ikili ağaçların yapısı kaynaklı (ekleme ve silme işlemlerine bağlı olarak) çeşitli dengesizlik durumları meydana gelebilmektedir. Bu dengesizlik durumlarının tespit edilip uygun tekniklerle dengelenmesi gerekmektedir. Bu sorunu gidermek amacıyla döndürme sistemi (sağa & sola döndürme) ile ağaç dengeleme işlemleri gerçekleştirilir. Ekleme ya da silme işleminden sonra, yükseklik dengeleme özelliği ihlal edilirse, dengeyi yeniden sağlamak için döndürme işlemleri uygulanır. Dengeli yapının korunması için yapılan döndürmeler ağacın yapısına göre değişmektedir. Yapılacak işlemin belirlendiği bu durumlar ise şu şekildedir;

1. Sol — Sol Dengesizliği (Left — Left Case)

• Bir düğümün sol alt ağacının sol alt ağacına bir düğüm eklendiğinde veya silindiğinde meydana gelir ve bu da ağaçta bir dengesizliğe neden olur.
• Düğümün sol çocuğunun denge faktörü 0 veya 1'dir ve sol çocuğun sol çocuğunun denge faktörü de 0 veya 1'dir.
• Dengeyi sağlamak için dengesiz düğüm sağa döndürülür.

2. Sağ — Sağ Dengesizliği (Right — Right Case)

• Bir düğümün sağ alt ağacının sağ alt ağacına bir düğüm eklendiğinde veya silindiğinde meydana gelir ve bu da ağaçta bir dengesizliğe neden olur.
• Düğümün sağ çocuğunun denge faktörü 0 veya 1'dir ve sağ çocuğun sağ çocuğunun denge faktörü de 0 veya 1'dir.
• Dengeyi sağlamak için dengesiz düğüm sola döndürülür.

3. Sol — Sağ Durumu (Left — Right Case)

• Sol alt ağacın sağ alt ağacına bir düğüm eklendiğinde veya silindiğinde gerçekleştirilir. Bu dengesizlik, sol çocuğun sol alt ağacının, sol çocuğun sağ alt ağacından daha uzun olması şeklinde kendini gösterir.
• Düğümün sol çocuğunun denge faktörü -1 ve sol çocuğun sağ çocuğunun denge faktörü 1'dir.
• Sol dönüşün ardından sağ dönüşün bir kombinasyonudur.

4. Sağ — Sol Durumu (Right — Left Case)

• Sağ alt ağacın sol alt ağacına bir düğüm eklenirse ya da silinirse gerçekleştirilir. Bu dengesizlik, sağ çocuğun sağ alt ağacının sağ çocuğun sol alt ağacından daha uzun olması şeklinde gösterilir.
• Düğümün sağ çocuğunun denge faktörü 1, sağ çocuğun sol çocuğunun denge faktörü -1'dir.
• Sağ dönüşün ardından sol dönüşün bir kombinasyonudur.

3.3 ZAMAN VE ALAN KARMAŞIKLIKLARI

AVL Ağaçlarının zaman ve alan karmaşıklığı analizini özetleyen şema aşağıda (Tablo 3.3.1.) verilmiştir. Bu tablo, AVL ağaçları üzerindeki yaygın işlemlerin ortalama ve en kötü durum karmaşıklığını özetlemektedir. AVL ağacının kendi kendini dengeleme özelliği, çoğu senaryoda verimli performans sağlayarak onu çok çeşitli uygulamalar için uygun hale getirmektedir.

3.4 AVL AĞAÇLARI KULLANIMI

AVL ağaçları, dengeli yapıları ve verimli davranışlarından dolayı birçok alanda yaygın olarak kullanılmaktadır. Bu sebeplerden bazıları şunlardır.

Dengeli Yapı: AVL ağaçlarının bir önceki başlıklarda da bahsedilmiş olan dengeli yapısı verimli arama, ekleme ve silme işlemleri yapılmasına olanak sağlar. Bu özellik sayesinde yapılan işlemlerin en kötü surum zaman karmaşıklığı O(log(n)) olmaktadır [18].

İşlemlerin Verimini Arttırma: AVL ağaçlarının sunduğu dengeli yapı dolayısıyla dengesiz ikili ağaç veri yapılarına kıyasla işlemler çok daha hızlı gerçekleştirilir [12].

Performans Garantisi: Yukarıdaki tabloda (Tablo 3.3.1) da gösterildiği üzere bu veri yapısında işlem ne olursa olsun en kötü senaryonun ne olduğu bilinir. En kötü durumun ön görülebilmesi ve tutarlı olması da gerçek zamanlı ve ve performans açısından kritik uygulamalar için önemli olmaktadır [24].

Dinamik Veri Kümeleri: AVL ağaçları, veri kümesi dinamik olduğunda özellikle kullanışlıdır. Ögelerin sık sık eklenip silindiği durumlarda AVL ağaçlarının kendini dengeleme özelliği ağacın verimli bir şekilde uyum sağlamasına ve dinamik güncellemeler sırasında kararlılığı ve verimli erişim sürelerini korumasına olanak tanımaktadır.

Veri Tabanı Dizinleme: AVL ağaçları genellikle veri tabanı sistemlerinde dizin yapıları olarak kullanılır. Hızlı bir arama ve alma süreci sağlarlar ve anahtar değerlere dayalı olarak kayıtları verimli bir şekilde almak için uygundurlar. AVL ağaçlarının dengeli doğası, dizin işlemlerini optimum zamansal karmaşıklıkla gerçekleştirilmesine izin verir [26–27].

Derleyici Uygulamaları: AVL ağaçları, derleyici tasarımında ve sembol tablosu yönetiminde kullanılır. Tanımlayıcıları, değişkenleri ve diğer dil yapılarını verimli bir şekilde depolamak ve almak için kullanılırlar. AVL ağacının dengeli doğası, derleme ve yorumlama sırasında sembol tablosu aramalarını hızlandırmaktadır [27].

Dosya Sistemleri: Dizin yapılarını korumak ve dosyaları verimli bir şekilde bulmak için dosya sistemlerinde kullanılır. Dizinler arasında hızlı gezinmeyi ve dosya meta verilerinin alınmasını sağlayarak verimli dosya yönetimi ve organizasyonuna katkıda bulunurlar [28].

Ağ Yönlendirmesi: AVL ağaçları, ağ yönlendirme algoritmalarında, özellikle İnternet Protokolü (IP) yönlendirme tablolarında kullanılır. Hızlı ve doğru yönlendirme kararlarını kolaylaştırarak, ağ ön eklerini depolamak ve aramak için verimli bir veri yapısı sağlarlar [29].

Dil İşleme: Yazım denetimi ve otomatik hata düzeltme gibi doğal dil işleme görevlerinde kullanılır. Hızlı arama ve önerilere sağladığı olanakkla, çok sayıda kelime veya kelime öbeğini verimli bir şekilde depolamaya ve almaya yardımcı olurlar [30].

Grafikler ve Geometri: AVL ağaçları bilgisayar grafikleri ve hesaplamalı geometride çarpışma tespiti veya uzamsal indeksleme gibi geometri algoritmalarını destekleyerek noktalar, çizgiler veya çokgenler gibi uzamsal verileri verimli bir şekilde düzenlemek amacıyla kullanılmaktadır [31].

Önbellek ve Bellek Yönetimi: Önbellek yönetimi, kullanım takibi ve optimum değiştirme kararları için verimli veri yapıları sağlamaktadırlar [32].

4. SONUÇ

Bu çalışma boyunca kendini dengeleyen ikili arama ağacı yapısına sahip iki önemli algoritma olan Kırmızı-Siyah Ağaç ve AVL Ağaç yapıları özellik, işlem, performans ve kullanım durumlarına göre incelenmiştir. Yapılan literatür araştırmaları sonucunda her iki veri yapısının da dengeli formunu korurken verimli arama, silme ve ekleme işlemlerini öngörülebilir ve garantili en kötü durum karmaşıklığı ile sunduğu gözlemlenmiştir.

Kırmızı-siyah ağaçların daha az sayıda döndürme işlemi ile daha basit bir dengeleme mekanizmasına sahip olduğu, bu sebeple ekleme ve silme işlemlerinin çok olduğu durumlarda tercih edilme ihtimalinin daha fazla olabileceği sonucu çıkarılmıştır. Bununla birlikte, kırmızı-siyah ağaçlara nazaran daha dengeli bir ağaç yapısı sağlayan AVL ağaçlarının daha hızlı arama performansı sunduğu gözlemlenmiştir. Bu iki algoritma arasındaki seçim, uygulamanın gereksinimlerine göre değişmekte olduğu için uygulama ihtiyaçlarının doğru anlaşılması ve ona göre karar alınması elzemdir.

5. KAYNAKÇA

[1] Robert. Sedgewick and Addison. Wesley. “Algorithms in Java, Parts 1–4. Professional. 768 pages”. 23 juil. 2002.

[4] Schütt, T., Schintke, F., & Skrzypczak, J. (2020). Transactions on Red-black and AVL trees in NVRAM. arXiv preprint arXiv:2006.16284.

[5] Leo J. Guibas and Robert Sedgewick. A dichromatic framework for balanced trees. In Foundations of Computer Science, 1978., 19th Annual Symposium on, pages 8–21, New York, NY, USA, 1978. IEEE Computer Society.

[6] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. ISBN 0262033844, 9780262033848.

[7] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). The MIT Press.

[8] Mehlhorn, K., & Sanders, P. (2008). Algorithms and Data Structures: The Basic Toolbox (3rd ed.). Springer.

[11] İnternet: https://www.geeksforgeeks.org/insertion-in-red-black-tree/

[12] Weiss, M. A. (2013). Data Structures and Algorithm Analysis in Java (3rd ed.). Pearson.

[13] Lozi, Jean-Pierre; Lepers, Baptiste; Funston, Justin; Gaud, Fabien; Quema, Vivian; Fedorova, Alexandra. “The Linux Scheduler: A Decade of Wasted Cores” (PDF). EuroSys 2016. Retrieved 15 June 2019.

[14] Li, T.; Baumberger, D.; Hahn, S. (2009). “Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin” (PDF). ACM SIGPLAN Notices. 44 (4): 65. CiteSeerX 10.1.1.567.2170. doi:10.1145/1594835.1504188.

[15] Love, Robert (2010). Linux Kernel Development (3rd ed.). United States of America: Addison Wesley. pp. 41–61.

[16] “Linux: The Completely Fair Scheduler | KernelTrap”. 2007–04–19. Archived from the original on 2007–04–19. Retrieved 2021–05–16.

[17] Molnár, Ingo (2007–04–13). “[patch] Modular Scheduler Core and Completely Fair Scheduler [CFS]”.

[18] Adelson-Velsky, G. M., & Landis, E. M. (1962). An algorithm for the organization of information. Doklady Akademii Nauk SSSR, 146(2), 263–266.

[19] Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.

[20] Sedgewick, R. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

[21] Weiss, M. A. (2014). Data structures and algorithm analysis in C++.

[22] Mehlhorn, K., & Sanders, P. (2008). Algorithms and Data Structures: The Basic Toolbox (3rd ed.). Springer. [23] Tarjan, R. E. (1983). Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics.

[23] Bentley, J. L. (1997). Programming Pearls (2nd ed.). Addison-Wesley Professional.

[24] Sedgewick, R. (2011). Algorithms (4th ed.). Addison-Wesley Professional.

[25] Open Data Structures — Chapter 14: Red-Black Trees. (n.d.). Retrieved from https://opendatastructures.org/ods-java/14_RedBlackTrees.html

[26] Garcia-Molina, H., Ullman, J. D., & Widom, J. (2008). Database Systems: The Complete Book (2nd ed.). Prentice Hall.

[27] Aho, A. V., Lam, M. S., Sethi, R., & Ullman, J. D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson.

[28] Silberschatz, A., Galvin, P. B., & Gagne, G. (2012). Operating System Concepts (9th ed.). John Wiley & Sons.

[29] Comer, D. E. (2000). Internetworking with TCP/IP: Principles, Protocols, and Architecture (4th ed.). Prentice Hall.

[30] Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.

[31] de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational Geometry: Algorithms and Applications (3rd ed.). Springer.

[32] Hennessy, J. L., & Patterson, D. A. (2011). Computer Architecture: A Quantitative Approach (5th ed.). Morgan Kaufmann.