başlangıç
Bu makale ikili arama ağaçları hakkındadır. Yakın zamanda bununla ilgili bir makale yazdım Orada ikili ağaçlara pek dikkat etmedim çünkü arama, ekleme ve silme yöntemleri konuyla alakalı değildi. Artık ağaçlarla ilgili bir makale yazmaya karar verdim. Başlayalım.
Ağaç, kenarlarla birbirine bağlanan düğümlerden oluşan bir veri yapısıdır. Ağacın grafiğin özel bir durumu olduğunu söyleyebiliriz. İşte örnek bir ağaç:
Bu bir ikili arama ağacı değil! Her şey kesildi!
terminoloji
kök
Ağaç kökü - bu onun en üst düğümüdür. Örnekte bu, A düğümüdür. Bir ağaçta, kökten herhangi bir başka düğüme yalnızca bir yol çıkabilir! Aslında herhangi bir düğüm, bu düğüme karşılık gelen alt ağacın kökü olarak düşünülebilir.
Ebeveynler / torunlar
Kök dışındaki tüm düğümlerin, başka bir düğüme giden tam olarak bir kenarı vardır. Geçerli düğümün üzerinde bulunan düğüme denir ebeveyn bu düğüm. Geçerli olanın altında bulunan ve ona bağlı olan düğüme denir azalan bu düğüm. Bir örnek kullanalım. B düğümünü alalım, o zaman ebeveyni A düğümü olacak ve çocukları D, E ve F düğümleri olacaktır.
Лист
Çocuğu olmayan bir düğüme ağacın yaprağı adı verilecektir. Örnekte yapraklar D, E, F, G, I, J, K düğümleri olacaktır.
Bu temel terminolojidir. Diğer kavramlar daha detaylı tartışılacaktır. Yani ikili ağaç, her düğümün ikiden fazla çocuğunun olmayacağı bir ağaçtır. Tahmin ettiğiniz gibi örnekteki ağaç ikili olmayacak çünkü B ve H düğümlerinin ikiden fazla çocuğu var. İşte bir ikili ağaç örneği:
Ağaç düğümleri her türlü bilgiyi içerebilir. İkili arama ağacı, aşağıdaki özelliklere sahip bir ikili ağaçtır:
- Hem sol hem de sağ alt ağaçlar ikili arama ağaçlarıdır.
- Rastgele bir X düğümünün sol alt ağacının tüm düğümleri, X düğümünün veri anahtarının değerinden daha düşük veri anahtarı değerlerine sahiptir.
- Rastgele bir X düğümünün sağ alt ağacındaki tüm düğümler, X düğümünün veri anahtarının değerinden daha büyük veya ona eşit veri anahtarı değerlerine sahiptir.
Anahtar — düğümün herhangi bir özelliği (örneğin bir sayı). Bu anahtarın karşılık geldiği ağaç öğesini bulabilmeniz için anahtara ihtiyaç vardır. İkili arama ağacı örneği:
Ağaç görünümü
İlerledikçe, anlayışınızı geliştirmek için bazı (muhtemelen eksik) kod parçaları sunacağım. Kodun tamamı makalenin sonunda olacaktır.
Bir ağaç düğümlerden oluşur. Düğüm yapısı:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
//...остальные методы узла
}
Her düğümün iki çocuğu vardır (leftChild ve/veya rightChild çocuklarının boş bir değer içermesi oldukça olasıdır). Muhtemelen bu durumda sayı verilerinin düğümde depolanan veriler olduğunu fark etmişsinizdir; anahtar – düğüm anahtarı.
Düğümü çözdük, şimdi ağaçlarla ilgili acil sorunlardan bahsedelim. Bundan sonra “ağaç” kelimesiyle ikili arama ağacı kavramını kastedeceğim. İkili ağaç yapısı:
public class BinaryTree<T> {
private Node<T> root;
//методы дерева
}
Bir sınıf alanı olarak yalnızca ağacın köküne ihtiyacımız var, çünkü kökten getLeftChild() ve getRightChild() yöntemlerini kullanarak ağaçtaki herhangi bir düğüme ulaşabilirsiniz.
Ağaçtaki algoritmalar
arama
Diyelim ki inşa edilmiş bir ağacınız var. Anahtar anahtarı olan bir öğe nasıl bulunur? Kökten ağaçta sırayla ilerlemeniz ve anahtarın değerini bir sonraki düğümün anahtarıyla karşılaştırmanız gerekir: eğer anahtar bir sonraki düğümün anahtarından küçükse, o zaman düğümün sol alt soyuna gidin, eğer öyleyse daha büyük, sağdaki tuşlar eşitse istenilen düğüm bulunur! İlgili kod:
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
Akım sıfırlanırsa, arama ağacın sonuna ulaşmış demektir (kavramsal düzeyde, ağaçta var olmayan bir yerdesiniz - bir yaprağın soyundan geliyorsunuz).
Arama algoritmasının etkinliğini dengeli bir ağaç (düğümlerin az çok eşit şekilde dağıtıldığı bir ağaç) üzerinde düşünelim. O zaman arama verimliliği O(log(n)) olacaktır ve logaritma 2 tabanına olacaktır. Bakın: eğer dengeli bir ağaçta n eleman varsa, o zaman bu, ağacın 2 tabanına kadar log(n) olacağı anlamına gelir. ağaç. Ve arama sırasında döngünün bir adımında bir seviye aşağıya inersiniz.
eklemek
Aramanın özünü kavrarsanız, eklemeyi anlamak sizin için zor olmayacaktır. Sadece ağacın bir yaprağına inmeniz (aramada açıklanan iniş kurallarına göre) ve onun soyundan olmanız (anahtara bağlı olarak sol veya sağ) olmanız yeterlidir. Uygulama:
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
Bu durumda mevcut düğüme ek olarak mevcut düğümün ebeveyni hakkındaki bilgilerin de saklanması gerekir. Akım null değerine eşit olduğunda ana değişken ihtiyacımız olan sayfayı içerecektir.
Eklemenin verimliliği açıkça arama - O(log(n)) ile aynı olacaktır.
Giderme
Kaldırma, bir ağaçta yapılması gereken en zor işlemdir. Öncelikle sileceğimiz öğeyi bulmamız gerekeceği açıktır. Peki ya sonra? Referansını null olarak ayarlarsak, bu düğümün kökü olduğu alt ağaç hakkındaki bilgileri kaybederiz. Ağaç kaldırma yöntemleri üç duruma ayrılır.
İlk vaka. Silinmekte olan düğümün alt öğesi yok
Silinen düğümün çocuğu yoksa bu onun bir yaprak olduğu anlamına gelir. Bu nedenle, ebeveyninin leftChild veya rightChild alanlarını null olarak ayarlayabilirsiniz.
İkinci vaka. Silinecek düğümün bir çocuğu var
Bu dava da çok karmaşık değil. Örneğimize dönelim. Diyelim ki 14 anahtarına sahip bir öğeyi silmemiz gerekiyor. Bu, 10 anahtarına sahip bir düğümün sağ soyundan olduğu için, onun soyundan herhangi birinin (bu durumda doğru olanın) 10'dan büyük bir anahtarı olacağını kabul edin; onu ağaçtan kolayca "kesebilir" ve ebeveyni doğrudan silinen düğümün çocuğuna bağlayabilir; 10 numaralı düğümü 13 numaralı düğüme bağlayın. Ebeveyninin sol çocuğu olan bir düğümün silinmesi gerekiyorsa durum benzer olacaktır. Kendiniz düşünün - tam bir benzetme.
Üçüncü durum. Bir düğümün iki çocuğu var
En zor durum. Yeni bir örneğe bakalım.
Bir halef arayın
Diyelim ki 25 numaralı düğümü silmemiz gerekiyor. Yerine kimi koymalıyız? Onun takipçilerinden biri (torunları veya soyundan gelenler) olmalı halef(kaldırılan düğümün yerini alacak kişi).
Kimin halefi olması gerektiğini nasıl anlayabilirim? Sezgisel olarak bu, anahtarı silinen düğümden sonraki en büyük olan ağaçtaki bir düğümdür. Algoritma aşağıdaki gibidir. Sağ soyundan gitmeniz gerekir (her zaman sağdakine, çünkü ardıl anahtarın silinen düğümün anahtarından daha büyük olduğu zaten söylenmişti) ve sonra bu sağ soyundan gelenlerin sol soyundan gelenler zincirinden geçmeniz gerekir. . Örnekte, 35 numaralı düğüme gidip, soldaki alt zincirlerden geçerek yaprağa ineceğiz - bu durumda, bu zincir yalnızca 30 numaralı düğümden oluşuyor. aradığımız düğümden daha büyük düğümler kümesindeki en küçük düğüm için.
Ardıl arama yöntemi kodu:
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;//родитель преемника
Node<T> successor = deleteNode;//преемник
Node<T> current = successor.getRightChild();//просто "пробегающий" узел
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
//на выходе из цикла имеем преемника и родителя преемника
if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
}
return successor;
}
Silme yönteminin tam kodu:
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;//В зависимости от того, является ли удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {//второй случай
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {//третий случай
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
Karmaşıklık O(log(n)) değerine yakınlaştırılabilir.
Bir ağaçta maksimum/minimum bulma
Bir ağaçta minimum/maksimum değerin nasıl bulunacağı açıktır - sırasıyla ağacın sol/sağ öğeleri zinciri boyunca sırayla hareket etmeniz gerekir; sayfaya ulaştığınızda minimum/maksimum öğe olacaktır.
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
Karmaşıklık - O(log(n))
Simetrik bypass
Geçiş, ağacın her bir düğümünü, onunla bir şeyler yapmak için ziyaret etmektir.
Özyinelemeli simetrik geçiş algoritması:
- Soldaki çocuk üzerinde bir işlem yapın
- Kendinizle bir eylem yapın
- Doğru çocuğa bir işlem yapın
Kod:
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
inOrder(current.getRightChild());
}
}
Sonuç
Nihayet! Herhangi bir şeyi açıklamadıysam veya herhangi bir yorumum varsa, lütfen bunları yorumlarda bırakın. Söz verdiğim gibi kodun tamamını veriyorum.
Node.java:
public class Node<T> {
private T data;
private int key;
private Node<T> leftChild;
private Node<T> rightChild;
public Node(T data, int key) {
this.data = data;
this.key = key;
}
public void setLeftChild(Node<T> newNode) {
leftChild = newNode;
}
public void setRightChild(Node<T> newNode) {
rightChild = newNode;
}
public Node<T> getLeftChild() {
return leftChild;
}
public Node<T> getRightChild() {
return rightChild;
}
public T getData() {
return data;
}
public int getKey() {
return key;
}
}
BinaryTree.java:
public class BinaryTree<T> {
private Node<T> root;
public Node<T> find(int key) {
Node<T> current = root;
while (current.getKey() != key) {
if (key < current.getKey())
current = current.getLeftChild();
else
current = current.getRightChild();
if (current == null)
return null;
}
return current;
}
public void insert(T insertData, int key) {
Node<T> current = root;
Node<T> parent;
Node<T> newNode = new Node<>(insertData, key);
if (root == null)
root = newNode;
else {
while (true) {
parent = current;
if (key < current.getKey()) {
current = current.getLeftChild();
if (current == null) {
parent.setLeftChild(newNode);
return;
}
}
else {
current = current.getRightChild();
if (current == null) {
parent.setRightChild(newNode);
return;
}
}
}
}
}
public Node<T> getMinimum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getLeftChild();
}
return parent;
}
public Node<T> getMaximum(Node<T> startPoint) {
Node<T> current = startPoint;
Node<T> parent = current;
while (current != null) {
parent = current;
current = current.getRightChild();
}
return parent;
}
public Node<T> getSuccessor(Node<T> deleteNode) {
Node<T> parentSuccessor = deleteNode;
Node<T> successor = deleteNode;
Node<T> current = successor.getRightChild();
while (current != null) {
parentSuccessor = successor;
successor = current;
current = current.getLeftChild();
}
if (successor != deleteNode.getRightChild()) {
parentSuccessor.setLeftChild(successor.getRightChild());
successor.setRightChild(deleteNode.getRightChild());
}
return successor;
}
public boolean delete(int deleteKey) {
Node<T> current = root;
Node<T> parent = current;
boolean isLeftChild = false;
while (current.getKey() != deleteKey) {
parent = current;
if (deleteKey < current.getKey()) {
current = current.getLeftChild();
isLeftChild = true;
} else {
isLeftChild = false;
current = current.getRightChild();
}
if (current == null)
return false;
}
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root)
current = null;
else if (isLeftChild)
parent.setLeftChild(null);
else
parent.setRightChild(null);
}
else if (current.getRightChild() == null) {
if (current == root)
root = current.getLeftChild();
else if (isLeftChild)
parent.setLeftChild(current.getLeftChild());
else
current.setRightChild(current.getLeftChild());
} else if (current.getLeftChild() == null) {
if (current == root)
root = current.getRightChild();
else if (isLeftChild)
parent.setLeftChild(current.getRightChild());
else
parent.setRightChild(current.getRightChild());
}
else {
Node<T> successor = getSuccessor(current);
if (current == root)
root = successor;
else if (isLeftChild)
parent.setLeftChild(successor);
else
parent.setRightChild(successor);
}
return true;
}
public void inOrder(Node<T> current) {
if (current != null) {
inOrder(current.getLeftChild());
System.out.println(current.getData() + " ");
inOrder(current.getRightChild());
}
}
}
PS
O(n)'ye Dejenerasyon
Birçoğunuz fark etmiş olabilirsiniz: Ağacın dengesini bozarsanız ne olur? Örneğin, artan anahtarlara sahip düğümleri bir ağaca yerleştirin: 1,2,3,4,5,6... O zaman ağaç bir şekilde bağlantılı bir listeye benzeyecektir. Ve evet, ağaç, ağaç yapısını ve dolayısıyla veri erişiminin verimliliğini kaybedecek. Arama, ekleme ve silme işlemlerinin karmaşıklığı bağlantılı listedekiyle aynı olacaktır: O(n). Bence ikili ağaçların en önemli dezavantajlarından biri bu.
Ankete sadece kayıtlı kullanıcılar katılabilir. Lütfen.
Uzun zamandır bu merkezde değildim ve hangi konularda daha fazla hangi makaleleri görmek istediğinizi bilmek isterim.
-
Veri yapıları
-
Algoritmalar (DP, özyineleme, veri sıkıştırma vb.)
-
Veri yapılarının ve algoritmaların gerçek hayatta uygulanması
-
Android Uygulamalarını Java ile Programlamak
-
Java ile web uygulamaları programlama
2 kullanıcı oy kullandı. 1 kullanıcı çekimser kaldı.
Kaynak: www.habr.com