Arama ağacı - Search tree
Gelen bilgisayar bilimleri , bir arama ağacı bir olan ağaç veri yapısı kümesi içinden belirli tuşlara bulmak için kullandı. Bir ağacın arama ağacı olarak işlev görmesi için, her düğümün anahtarının, soldaki alt ağaçlardaki herhangi bir anahtardan daha büyük ve sağdaki alt ağaçlardaki herhangi bir anahtardan daha küçük olması gerekir.
Arama ağaçlarının avantajı, ağacın makul ölçüde dengeli olduğu, yani her iki uçtaki yaprakların karşılaştırılabilir derinliklere sahip olduğu göz önüne alındığında, verimli arama süreleridir . Çeşitli arama ağacı veri yapıları mevcuttur, bunların birçoğu aynı zamanda elemanların verimli bir şekilde eklenmesine ve silinmesine izin verir, bu işlemler daha sonra ağaç dengesini korumak zorundadır.
Arama ağaçları genellikle bir ilişkisel diziyi uygulamak için kullanılır . Arama ağacı algoritması, bir konum bulmak için anahtar/değer çiftindeki anahtarı kullanır ve ardından uygulama, tüm anahtar/değer çiftini o belirli konumda depolar.
Ağaç Türleri
İkili arama ağacı
İkili Arama Ağacı, her düğümün bir anahtar ve sol ve sağ olmak üzere iki alt ağaç içerdiği düğüm tabanlı bir veri yapısıdır. Tüm düğümler için, sol alt ağacın anahtarı, düğümün anahtarından küçük olmalı ve sağ alt ağacın anahtarı, düğümün anahtarından büyük olmalıdır. Bu alt ağaçların tümü ikili arama ağaçları olarak nitelendirilmelidir.
Bir ikili arama ağacını aramak için en kötü durum zaman karmaşıklığı , n elemanlı bir ağaç için O(log n) kadar küçük olabilen ağacın yüksekliğidir .
B ağacı
B-ağaçları, her bir düğümde değişken sayıda alt ağaçlara sahip olabildikleri için ikili arama ağaçlarının genellemeleridir. Alt düğümler önceden tanımlanmış bir aralığa sahip olsa da, mutlaka verilerle doldurulmayacaklardır, yani B ağaçları potansiyel olarak biraz yer israf edebilir. Avantajı, B-ağaçlarının diğer kendi kendini dengeleyen ağaçlar kadar sık yeniden dengelenmesine gerek olmamasıdır .
Düğüm uzunluklarının değişken aralığı nedeniyle, B ağaçları büyük veri bloklarını okuyan sistemler için optimize edilmiştir, ayrıca veritabanlarında da yaygın olarak kullanılırlar.
Bir B ağacını aramak için zaman karmaşıklığı O(log n)'dir.
(a,b)-ağaç
Bir (a,b)-ağacı, tüm yapraklarının aynı derinlikte olduğu bir arama ağacıdır. Her düğümün en az bir çocuğu ve en fazla b çocuğu varken, kökün en az 2 ve en fazla b çocuğu vardır.
a ve b'ye aşağıdaki formülle karar verilebilir:
Bir (a,b)-ağacı aramak için zaman karmaşıklığı O(log n)'dir.
Üçlü arama ağacı
Üçlü arama ağacı, 3 düğüme sahip olabilen bir ağaç türüdür: düşük çocuk, eşit çocuk ve yüksek çocuk. Her düğüm tek bir karakter depolar ve ağacın kendisi, olası bir üçüncü düğüm dışında ikili arama ağacıyla aynı şekilde sıralanır.
Üçlü bir arama ağacının aranması, herhangi bir yolun onu içerip içermediğini test etmek için bir dizgenin geçirilmesini içerir.
Dengeli bir üçlü arama ağacını aramak için zaman karmaşıklığı O(log n)'dir.
Arama algoritmaları
Belirli bir anahtarı arama
Ağacın sıralı olduğunu varsayarsak, bir anahtar alabilir ve onu ağacın içinde bulmaya çalışabiliriz. Aşağıdaki algoritmalar ikili arama ağaçları için genelleştirilmiştir, ancak aynı fikir diğer formatlardaki ağaçlara da uygulanabilir.
özyinelemeli
search-recursive(key, node)
if node is NULL
return EMPTY_TREE
if key < node.key
return search-recursive(key, node.left)
else if key > node.key
return search-recursive(key, node.right)
else
return node
yinelemeli
searchIterative(key, node)
currentNode := node
while currentNode is not NULL
if currentNode.key = key
return currentNode
else if currentNode.key > key
currentNode := currentNode.left
else
currentNode := currentNode.right
Min ve max aranıyor
Sıralanmış bir ağaçta, minimum, en soldaki düğümde bulunurken, maksimum, en sağdaki düğümde bulunur.
Asgari
findMinimum(node)
if node is NULL
return EMPTY_TREE
min := node
while min.left is not NULL
min := min.left
return min.key
Maksimum
findMaximum(node)
if node is NULL
return EMPTY_TREE
max := node
while max.right is not NULL
max := max.right
return max.key