Aralık ağacı - Interval tree
İçinde bilgisayar Bilimi, bir aralık ağacı bir ağaç veri yapısı tutmak aralıklar. Spesifik olarak, herhangi bir aralık veya nokta ile örtüşen tüm aralıkların verimli bir şekilde bulunmasına izin verir. Sıklıkla[kaynak belirtilmeli ] pencereleme sorguları için, örneğin, dikdörtgen bir görünüm penceresi içindeki bilgisayarlı bir haritada tüm yolları bulmak veya üç boyutlu bir sahne içindeki tüm görünür öğeleri bulmak için kullanılır. Benzer bir veri yapısı, segment ağacı.
Önemsiz çözüm, her aralığı ziyaret etmek ve verilen nokta veya aralık ile kesişip kesişmediğini test etmektir. zaman, nerede koleksiyondaki aralıkların sayısıdır. Bir sorgu tüm aralıkları döndürebileceğinden, örneğin sorgu koleksiyondaki tüm aralıklarla kesişen büyük bir aralıksa, bu asimptotik olarak optimal; ancak, düşünerek daha iyisini yapabiliriz çıktıya duyarlı algoritmalar, çalışma zamanının terimleriyle ifade edildiği , sorgu tarafından üretilen aralıkların sayısı. Aralık ağaçlarının sorgu süresi var ve ilk oluşturma zamanı hafıza tüketimini sınırlandırırken . Oluşturulduktan sonra, aralık ağaçları dinamik olabilir ve bir aralığın verimli bir şekilde eklenmesine ve silinmesine izin verebilir. zaman. Aralıkların uç noktaları küçük bir tam sayı aralığı içindeyse (Örneğin., aralıkta ), daha hızlı ve aslında optimal veri yapıları mevcuttur[1][2] ön işleme süresi ile ve sorgu zamanı raporlama için belirli bir sorgu noktasını içeren aralıklar (bkz.[1] çok basit bir tane için).
Naif yaklaşım
Basit bir durumda, aralıklar üst üste gelmez ve basit bir ikili arama ağacı ve sorgulandı zaman. Bununla birlikte, keyfi olarak çakışan aralıklarla, başlangıç noktalarına veya bitiş noktalarına göre sıralanan sıralamalar farklı olabileceğinden, ağaca eklemek için iki aralığı karşılaştırmanın bir yolu yoktur. Saf bir yaklaşım, biri başlangıç noktasına göre sıralanmış ve diğeri her aralığın bitiş noktasına göre sıralanmış iki paralel ağaç inşa etmek olabilir. Bu, her ağacın yarısının ancak sonuçların birleştirilmesi gerekir, zaman. Bu bize sorgular verir Bu kaba kuvvetten daha iyi değildir.
Aralık ağaçları bu sorunu çözer. Bu makalede, bir aralık ağacı için iki alternatif tasarım açıklanmaktadır. ortalanmış aralık ağacı ve büyütülmüş ağaç.
Ortalanmış aralık ağacı
Sorgular gerektirir zamanla toplam aralık sayısı ve rapor edilen sonuçların sayısıdır. İnşaat gerektirir zaman ve depolama gerektirir Uzay.
İnşaat
Bir dizi verildiğinde sayı doğrusundaki aralıklarda, başka bir aralık veya noktayla örtüşen tüm aralıkları verimli bir şekilde alabilmemiz için bir veri yapısı oluşturmak istiyoruz.
Tüm aralıkların tüm aralığını alıp ikiye bölerek başlarız. (uygulamada, ağacı nispeten dengeli tutmak için seçilmelidir). Bu, aralığın tamamen solundakiler olmak üzere üç set aralık verir biz arayacağız , tamamen sağındakiler biz arayacağız ve örtüşenler biz arayacağız .
Aralıklar ve hiç aralık kalmayana kadar aynı şekilde yinelemeli olarak bölünür.
Aralıklar merkez noktayla örtüşen, aralık ağacındaki düğüme bağlı ayrı bir veri yapısında saklanır. Bu veri yapısı, biri başlangıç noktalarına göre sıralanmış tüm aralıkları içeren ve diğeri bitiş noktalarına göre sıralanmış tüm aralıkları içeren iki listeden oluşur.
Sonuç bir ikili ağaç her düğüm şunları depolayarak:
- Bir merkez noktası
- Merkez noktanın tamamen solundaki tüm aralıkları içeren başka bir düğüme işaretçi
- Merkez noktasının tamamen sağındaki tüm aralıkları içeren başka bir düğüme işaretçi
- Merkez noktayla örtüşen tüm aralıklar, başlangıç noktalarına göre sıralanır
- Merkez noktayla örtüşen tüm aralıklar, bitiş noktalarına göre sıralanır
Kesişen
Yukarıda oluşturulan veri yapısı göz önüne alındığında, aralıklardan veya noktalardan oluşan sorgular alırız ve bu girdiyle örtüşen orijinal kümedeki tüm aralıkları döndürürüz.
Bir noktayla
Görev, ağaçta belirli bir noktayla çakışan tüm aralıkları bulmaktır. . Ağaç, geleneksel bir ikili ağacın üzerinden geçmek için kullanılana benzer bir özyinelemeli algoritma ile, ancak her düğümde "merkez" noktasının üst üste binen aralıkları aramayı desteklemek için ekstra mantıkla yürür.
Her ağaç düğümü için, karşılaştırılır , yukarıdaki düğüm yapımında kullanılan orta nokta. Eğer daha az , en soldaki aralık kümesi, , düşünülmektedir. Eğer daha büyüktür , en sağdaki aralık kümesi, , düşünülmektedir.
Her bir düğüm ağacı kökten yaprağa geçerken işlendiğinden, düğümlerindeki aralıklar işlem görüyor. Eğer daha az tüm aralıkların sonra biter veya üst üste gelemezlerdi . Bu nedenle, yalnızca bu aralıkları bulmamız gerekiyor bu daha önce başlıyor . Listelerine bakabiliriz zaten inşa edilmiş. Bu senaryoda sadece aralık başlangıçlarını önemsediğimiz için, başlangıçlara göre sıralanmış listeye başvurabiliriz. Şundan büyük olmayan en yakın sayıyı bulduğumuzu varsayalım bu listede. Listenin başlangıcından bulunan noktaya kadar tüm aralıklar çakışıyor çünkü daha önce başlıyorlar ve sonra biter (bildiğimiz gibi, çünkü birbirleriyle örtüşüyorlar hangisi daha büyük ). Böylece, başlangıç noktası değeri aşana kadar listedeki aralıkları numaralandırmaya başlayabiliriz. .
Aynı şekilde, eğer daha büyüktür tüm aralıkların önce başlamalı , bu yüzden sonra biten aralıkları buluruz aralık sonlarına göre sıralanmış listeyi kullanarak.
Eğer tam olarak eşleşir , tüm aralıklar daha fazla işlem yapılmadan sonuçlara eklenebilir ve ağaç geçişi durdurulabilir.
Bir aralık ile
Sonuç aralığı için sorgu aralığımızı kesişmek için aşağıdakilerden biri olmalıdır:
- başlangıç ve / veya bitiş noktası içinde ; veya
- tamamen çevreler .
Bu makale olabilir kafa karıştırıcı veya belirsiz okuyuculara.Şubat 2020) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) ( |
Önce içinde başlangıç ve / veya bitiş noktaları olan tüm aralıkları buluruz ayrı inşa edilmiş bir ağaç kullanarak. Tek boyutlu durumda, aralık kümesindeki tüm başlangıç ve bitiş noktalarını içeren bir arama ağacı kullanabiliriz, her biri karşılık gelen aralığa bir işaretçiye sahiptir. Bir ikili arama başlangıç ve bitiş zamanı dikkate alınması gereken minimum ve maksimum noktaları ortaya çıkarır. Bu aralıktaki her nokta, örtüşen bir aralığa başvurur ve sonuç listesine eklenir. Yinelemelerden kaçınmak için özen gösterilmelidir, çünkü bir aralık içinde hem başlayıp hem de bitebilir. . Bu, sonuç kümesine eklenip eklenmediğini işaretlemek için her aralıkta ikili bayrak kullanılarak yapılabilir.
Son olarak, çevreleyen aralıklar bulmalıyız . Bunları bulmak için içeride herhangi bir noktayı seçeriz ve bu noktayı kesen tüm aralıkları bulmak için yukarıdaki algoritmayı kullanın (yine, kopyaları kaldırmaya dikkat edin).
Daha yüksek boyutlar
Aralık ağacı veri yapısı daha yüksek bir boyuta genelleştirilebilir aynı sorgu ve yapım süresi ile ve Uzay.
İlk olarak, bir menzil ağacı içinde sorgu bölgesi içindeki başlangıç ve bitiş noktaları ile tüm aralıkların verimli bir şekilde alınmasını sağlayan boyutlar oluşturulmuştur . Karşılık gelen aralıklar bulunduğunda, geriye kalan tek şey, bölgeyi bir boyutta çevreleyen aralıklardır. Bu örtüşmeleri bulmak için, aralık ağaçları oluşturulur ve bir eksen kesişir her biri için sorgulanır. Örneğin, iki boyutta karenin altı (veya kesişen başka bir yatay çizgi ) yatay eksen için oluşturulan aralık ağacına karşı sorgulanacaktır. Aynı şekilde, sol (veya kesişen başka bir dikey çizgi) ) dikey eksende oluşturulan aralık ağacına karşı sorgulanabilir.
Her aralık ağacının daha yüksek boyutlar için eklenmesi gerekir. Her düğümde ağaçta ilerleriz, ile karşılaştırılır çakışmaları bulmak için. Tek boyutlu durumda kullanılan iki sıralı nokta listesi yerine, bir menzil ağacı oluşturulur. Bu, tüm noktaların verimli bir şekilde alınmasını sağlar. o örtüşen bölge .
Silme
Ağaçtan bir aralığı sildikten sonra, bu aralığı içeren düğüm başka aralık içermiyorsa, bu düğüm ağaçtan silinebilir. Bu, normal bir ikili ağaç silme işleminden daha karmaşıktır.
Bir aralık, ağaçtaki birkaç düğümün merkez noktasıyla çakışabilir. Her düğüm, sağ alt ağaç için benzer şekilde, sol alt ağaçtaki tüm aralıklarla merkez noktasının tamamen solunda olacak şekilde, üst üste gelen aralıkları depoladığından, her aralığın, kümeden köke en yakın düğümde saklandığını izler. merkez noktası örtüşen düğümler.
İkili bir ağaçtaki normal silme işlemleri (silinen düğümün iki çocuğu olduğu durumlarda), yapraktan daha uzaktaki bir düğümün silinen düğümün konumuna (genellikle sağ alt ağacın en sol alt öğesi veya en sağdaki alt) yükseltmeyi içerir. sol alt ağacın).
Bu yükseltmenin bir sonucu olarak, yükseltilen düğümün üzerindeki bazı düğümler onun soyundan gelecektir; bu düğümleri yükseltilmiş düğümle örtüşen aralıklar için araştırmak ve bu aralıkları yükseltilmiş düğüme taşımak gerekir. Sonuç olarak, bu, aynı algoritmayı tekrar izleyerek silinmesi gereken yeni boş düğümlerle sonuçlanabilir.
Dengeleme
Silme işlemini etkileyen aynı sorunlar, rotasyon işlemlerini de etkiler; rotasyon, düğümlerin köke mümkün olduğu kadar yakın depolandığı değişmezi korumalıdır.
Artırılmış ağaç
Aralıkları temsil etmenin başka bir yolu şu şekilde açıklanmıştır: Cormen vd. (2009, Bölüm 14.3: Aralık ağaçları, sayfa 348–354).
Hem ekleme hem de silme işlemi gerektirir zamanla ekleme veya silme işleminden önce ağaçtaki toplam aralık sayısıdır.
Bir artırılmış ağaç basit sıralı bir ağaçtan yapılabilir, örneğin bir ikili arama ağacı veya kendini dengeleyen ikili arama ağacı, aralıkların 'düşük' değerlerine göre sıralanır. Daha sonra her düğüme fazladan bir açıklama eklenir ve bu düğümden aşağıya doğru tüm aralıklar arasında maksimum üst değer kaydedilir. Bu özelliğin sürdürülmesi, bir düğüm eklendiğinde veya silindiğinde, düğümün tüm atalarının aşağıdan yukarıya güncellenmesini içerir. Bu yalnızca O alır (h) düğüm ekleme veya kaldırma başına adımlar, burada h ağaçta eklenen veya kaldırılan düğümün yüksekliğidir. Eğer varsa ağaç rotasyonları ekleme ve silme sırasında, etkilenen düğümlerin de güncellenmesi gerekebilir.
Artık iki aralık olduğu biliniyor ve sadece ikisi birden ve . Ağaçlarda belirli bir aralıkla örtüşen düğümleri ararken, hemen atlayabilirsiniz:
- düşük değeri verilen aralığın sonunu geçen düğümlerin sağındaki tüm düğümler.
- maksimum yüksek değeri verilen aralığın başlangıcından düşük olan tüm düğümler.
Üyelik sorguları
Ağaç gereksiz geçişleri önlerse bir miktar performans elde edilebilir. Bunlar, zaten var olan aralıkları eklerken veya var olmayan aralıkları kaldırırken ortaya çıkabilir.
Aralıklar üzerinde, önce alt sınırlarına ve sonra üst sınırlarına göre sıralanarak bir toplam düzen tanımlanabilir. Daha sonra üyelik kontrolü yapılabilir. zamana karşı kopyaları bulmak için gereken süre, eğer aralıklar, eklenecek veya çıkarılacak aralıkla örtüşüyor. Bu çözüm, herhangi bir ek yapı gerektirmeme avantajına sahiptir. Değişiklik kesinlikle algoritmiktir. Dezavantajı, üyelik sorgularının zaman.
Alternatif olarak, oranında bellek, beklenen sabit zamandaki üyelik sorguları, aralık ağacı ile kilit adımında güncellenen bir karma tablo ile uygulanabilir. Aralıklar değer yerine referans olarak saklanıyorsa bu, toplam bellek gereksinimini ikiye katlamayabilir.
Java örneği: Ağaca yeni bir aralık ekleme
Her düğümün anahtarı aralığın kendisidir, bu nedenle düğümler önce düşük değere ve son olarak yüksek değere göre sıralanır ve her düğümün değeri aralığın bitiş noktasıdır:
halka açık geçersiz Ekle(Aralık ben) { koymak(ben, ben.getEnd()); }
Java örneği: Ağaçta bir nokta veya aralık arama
Bir aralığı aramak için, kişi (n.getKey ()
) ve yüksek değerli (n.getValue ()
) sorguyla örtüşemeyen dalları atlamak için. En basit durum, nokta sorgusudur:
// ile başlayarak "p" içeren tüm aralıkları arayın // "n" düğümü ve "sonuç" listesine eşleşen aralıklar ekleme halka açık geçersiz arama(IntervalNode n, Nokta p, Liste<Aralık> sonuç) { // Var olmayan düğümleri aramayın Eğer (n == boş) dönüş; // Eğer p herhangi bir aralığın en sağ noktasının sağındaysa // bu düğümde ve tüm alt öğelerde herhangi bir eşleşme olmayacak. Eğer (p.karşılaştırmak(n.Değer elde etmek()) > 0) dönüş; // Sol çocukları ara arama(n.getLeft(), p, sonuç); // Bu düğümü kontrol edin Eğer (n.anahtarı al().içerir(p)) sonuç.Ekle(n.anahtarı al()); // p bu aralığın başlangıcının solundaysa, // o zaman sağdaki herhangi bir çocukta olamaz. Eğer (p.karşılaştırmak(n.anahtarı al().getStart()) < 0) dönüş; // Aksi takdirde, doğru çocukları ara arama(n.getRight(), p, sonuç); }
nerede
a.karşılaştırmak(b)
aa.karşılaştırmak(b)
a = b ise sıfır döndürüra.karşılaştırmak(b)
a> b ise pozitif bir değer döndürür
Bir aralığı aramak için kullanılan kod, ortadaki kontrol dışında benzerdir:
// Bu düğümü kontrol edin Eğer (n.anahtarı al().overlapsWith(ben)) sonuç.Ekle (n.anahtarı al());
overlapsWith () olarak tanımlanır:
halka açık Boole overlapsWith(Aralık diğer) { dönüş Başlat.karşılaştırmak(diğer.getEnd()) <= 0 && son.karşılaştırmak(diğer.getStart()) >= 0; }
Daha yüksek boyutlar
Artırılmış ağaçlar, ağacın her seviyesindeki boyutlar arasında geçiş yapılarak daha yüksek boyutlara genişletilebilir. Örneğin, iki boyut için, ağacın tek seviyeleri, x-koordineli, çift düzeyler ise y-koordinat. Bu yaklaşım, veri yapısını artırılmış bir ikili ağaçtan artırılmış bir kd ağacı, dolayısıyla ekleme ve silme işlemleri için dengeleme algoritmalarını önemli ölçüde karmaşıklaştırır.
Daha basit bir çözüm, iç içe geçmiş aralık ağaçları kullanmaktır. İlk olarak, için aralıkları kullanarak bir ağaç oluşturun. y-koordinat. Şimdi, ağaçtaki her düğüm için, üzerine başka bir aralık ağacı ekleyin. xtüm elemanlar için aralıklar y-range, bu düğümünki ile aynıdır y-Aralık.
Bu çözümün avantajı, aynı kod tabanı kullanılarak rastgele sayıda boyuta genişletilebilmesidir.
İlk başta, iç içe geçmiş ağaçların ek maliyeti engelleyici görünebilir, ancak bu genellikle böyle değildir. Daha önceki iç içe olmayan çözümde olduğu gibi, her biri için bir düğüm gerekir. x- her iki çözüm için aynı sayıda düğüm veren koordinat. Tek ek yük, dikey aralık başına bir tane olmak üzere iç içe geçmiş ağaç yapılarıdır. Bu yapı genellikle ihmal edilebilir boyuttadır, yalnızca kök düğüme bir göstericiden ve muhtemelen düğüm sayısı ve ağacın derinliğinden oluşur.
Medial veya uzunluk odaklı ağaç
Ortaya veya uzunluğa yönelik bir ağaç, artırılmış bir ağaca benzer, ancak aralıkların orta noktalarına göre sıralanmış ikili arama ağacı ile simetriktir. Maksimum odaklı bir ikili yığın her düğümde, aralığın uzunluğuna (veya uzunluğun yarısı) göre sıralanır. Ayrıca her düğümde alt ağacın minimum ve maksimum olası değerini (dolayısıyla simetriyi) saklarız.
Örtüşme testi
Yalnızca iki aralığın başlangıç ve bitiş değerlerini kullanma , için çakışma testi şu şekilde yapılabilir:
ve
Bu, toplam ve fark kullanılarak basitleştirilebilir:
Bu da çakışma testini şu şekilde azaltır:
Aralık ekleniyor
Ağaca yeni aralıklar eklemek, orta değeri anahtar olarak kullanan bir ikili arama ağacıyla aynıdır. Biz iteriz düğüm ile ilişkili ikili yığın üzerine ve tüm yüksek düğümlerle ilişkili minimum ve maksimum olası değerleri güncelleyin.
Tüm örtüşen aralıkları arama
Kullanalım sorgu aralığı için ve bir düğümün anahtarı için (ile karşılaştırıldığında aralıklarla)
Kök düğümden başlayarak, her bir düğümde, önce minimum ve maksimum düğüm değerlerini kullanarak sorgu aralığımızın düğüm alt ağacı ile çakışmasının mümkün olup olmadığını kontrol ederiz (eğer değilse, bu düğüm için devam etmiyoruz).
Sonra hesaplıyoruz bu düğüm (alt öğeleri değil) içindeki aralıkların sorgu aralığı ile örtüşmesi için (bilerek ):
ve onun ikili yığını üzerinde bir sorgu gerçekleştirin daha büyük
Sonra aynı şeyi yaparak düğümün hem sol hem de sağ çocuklarından geçiyoruz.
En kötü durumda, ikili arama ağacının tüm düğümlerini taramamız gerekir, ancak ikili yığın sorgusu optimum olduğu için bu kabul edilebilir (2 boyutlu bir problem her iki boyutta da optimum olamaz)
Bu algoritmanın, arama işlemleri için geleneksel bir aralık ağacından (artırılmış ağaç) daha hızlı olması beklenmektedir. Büyüme sırası aynı olsa da, öğelerin eklenmesi pratikte biraz daha yavaştır.
Referanslar
- ^ a b Jens M. Schmidt. Küçük Tamsayı Aralıklarında Aralıklı Saplama Sorunları. DOI. ISAAC'09, 2009
- ^ Aralık Sorguları # Yarı grup operatörleri
- Mark de Berg, Marc van Kreveld, Overmars'ı İşaretle, ve Otfried Schwarzkopf. Hesaplamalı Geometri, İkinci Revize Edilmiş Baskı. Springer-Verlag 2000. Bölüm 10.1: Aralık Ağaçları, s. 212–217.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009), Algoritmalara Giriş (3. baskı), MIT Press ve McGraw-Hill, ISBN 978-0-262-03384-8
- Franco P. Preparata ve Michael Ian Shamos. Hesaplamalı Geometri: Giriş. Springer-Verlag, 1985
Dış bağlantılar
- CGAL: C ++ 'da Hesaplamalı Geometri Algoritmaları Kitaplığı Güçlü bir Range Trees uygulamasını içerir
- Boost.Icl aralık kümelerinin ve haritaların C ++ uygulamalarını sunar.
- IntervalTree (Python) - etiketli aralıklarla uyumlu, AVL dengelemeli bir ortalanmış aralık ağacı
- Aralık Ağacı (C #) - AVL dengelemeli artırılmış bir aralık ağacı
- Aralık Ağacı (Ruby) - etiketli aralıklarla uyumlu, değişmez, ortalanmış bir aralık ağacı
- IntervalTree (Java) - AVL dengelemeli, örtüşme, bulma, Toplama arabirimi, id ile ilişkili aralıkları destekleyen artırılmış bir aralık ağacı