Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
İkili arama ağacı, verileri organize etmek için kullanılan bir çeşit . İkili ağaçtan temel farkı, verilerin sıralanmış bir şekilde tutulmasıdır, bu sayede ikili arama algoritmasının kullanılmasına imkân verir.
İkili arama ağaçlarında; her düğümün sağ çocuğu kendisinden büyük, sol çocuğu ise kendisinden küçüktür. Bu ağaçlarda çalışan arama algoritması önce kökten başlar, eğer aranan eleman kökten büyükse sağ çocuğa, kökten küçükse sol çocuğa ilerler. Böylece, eleman bulunana yapraklara kadar yinelemeli bir şekilde ilerleme sağlanır.
İşlemler
İkili arama ağacı üzerinde; arama, ekleme, silme işlemleri yapılabilir.
Arama
Kökten başlanarak arama işlemi yapılır. Eğer aranan eleman o anki düğümden büyükse sağa, küçükse sola ilerlenir. Bu algoritma bir döngü içinde ya da özyinelemeli şekilde uygulanabilir. Python kodu şu şekildedir:
def search_recursively(key, node): if node is None or node.key == key: return node if key < node.key: return search_recursively(key, node.left) # key > node.key return search_recursively(key, node.right) def search_iteratively(key, node): current_node = node while current_node is not None: if key == current_node.key: return current_node elif key < current_node.key: current_node = current_node.left else: # key > current_node.key: current_node = current_node.right return current_node Ekleme
Eleman ekleme işlemi her zaman yapraklara ya da tek çocuğu olan düğümlere yapılır. Bunun için öncelikle eklenecek elemanın konumu bulunmalıdır, konum bulma işlemi arama kısmında olduğu gibi büyükse sağa, küçükse sola ilerle şeklinde yapılır. Bu algoritma da bir döngü içinde ya da özyinelemeli şekilde uygulanabilir. kodu şu şekildedir:
Node* insert(Node*& root, int key, int value) { if (!root) root = new Node(key, value); else if (key < root->key) root->left = insert(root->left, key, value); else // key >= root->key root->right = insert(root->right, key, value); return root; Silme
Silme işlemi üç başlık altında incelenebilir. Eğer,
- Silinecek düğümün çocuğu yoksa: basitçe düğüm silinir.
- Silinecek düğümün tek çocuğu varsa: düğüm silinir ve tek çocuk silinen düğümün yerine taşınır.
- Silinecek düğümün iki çocuğu varsa: silinecek düğüme D diyelim, D'yi silmeden önce D'den büyük en küçük eleman bulunur (inorder successor) buna da E diyelim. E ile D yer değiştirilir ve ardından D silinir.
Bir elemandan büyük en küçük eleman, o elemanın sağ alt ağacının en solundaki elemandır ve bunu bulmak için ekstra metot yazmak gerekir. Bu yüzden, silme algoritması ekleme ve arama algoritmalarına göre daha uzundur. Python kodu şu şekildedir:
def find_min(self): # Gets minimum node in a subtree current_node = self while current_node.left_child: current_node = current_node.left_child return current_node def replace_node_in_parent(self, new_value=None): if self.parent: if self == self.parent.left_child: self.parent.left_child = new_value else: self.parent.right_child = new_value if new_value: new_value.parent = self.parent def binary_tree_delete(self, key): if key < self.key: self.left_child.binary_tree_delete(key) elif key > self.key: self.right_child.binary_tree_delete(key) else: # delete the key here if self.left_child and self.right_child: # if both children are present successor = self.right_child.find_min() self.key = successor.key successor.binary_tree_delete(successor.key) elif self.left_child: # if the node has only a *left* child self.replace_node_in_parent(self.left_child) elif self.right_child: # if the node has only a *right* child self.replace_node_in_parent(self.right_child) else: # this node has no children self.replace_node_in_parent(None) Dengeli ikili arama ağaçları
Bir ağaçtaki tüm düğümlerin sağ alt ağaçları ve sol alt ağaçları arasındaki yükseklik farkı en fazla 1 ise, o ağaç dengeli olarak tanımlanır. Ağaçların dengeli olması onların yüksekliğini azaltarak ağaç üzerinde çalışan algoritmaların performansını arttırır. Örneğin boş bir ikili arama ağacına 1, 2, 3, 4, 5, 6, 7 elemanlarını sırayla eklediğimizi düşünelim. Bu durumda elemanlar hep sağ tarafa ekleneceği için ağaç esasen bir bağlı listeye dönüşür. Halbuki, aynı elemanlar, yüksekliği 3 olan bir ağaca da yerleştirilebilirlerdi. Bu durum, dengeli ikili arama ağaçlarının icadına yol açmıştır. AVL ağacı, ve kırmızı-siyah ağaçlar dengeli ağaçlara örnektir.
wikipedia, wiki, viki, vikipedia, oku, kitap, kütüphane, kütübhane, ara, ara bul, bul, herşey, ne arasanız burada,hikayeler, makale, kitaplar, öğren, wiki, bilgi, tarih, yukle, izle, telefon için, turk, türk, türkçe, turkce, nasıl yapılır, ne demek, nasıl, yapmak, yapılır, indir, ücretsiz, ücretsiz indir, bedava, bedava indir, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, resim, müzik, şarkı, film, film, oyun, oyunlar, mobil, cep telefonu, telefon, android, ios, apple, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, pc, web, computer, bilgisayar
Ikili arama agaci verileri organize etmek icin kullanilan bir cesit Ikili agactan temel farki verilerin siralanmis bir sekilde tutulmasidir bu sayede ikili arama algoritmasinin kullanilmasina imkan verir 9 elemanli yuksekligi 4 ve koku 8 olan bir ikili arama agaci Ikili arama agaclarinda her dugumun sag cocugu kendisinden buyuk sol cocugu ise kendisinden kucuktur Bu agaclarda calisan arama algoritmasi once kokten baslar eger aranan eleman kokten buyukse sag cocuga kokten kucukse sol cocuga ilerler Boylece eleman bulunana yapraklara kadar yinelemeli bir sekilde ilerleme saglanir IslemlerIkili arama agaci uzerinde arama ekleme silme islemleri yapilabilir Arama Kokten baslanarak arama islemi yapilir Eger aranan eleman o anki dugumden buyukse saga kucukse sola ilerlenir Bu algoritma bir dongu icinde ya da ozyinelemeli sekilde uygulanabilir Python kodu su sekildedir def search recursively key node if node is None or node key key return node if key lt node key return search recursively key node left key gt node key return search recursively key node right def search iteratively key node current node node while current node is not None if key current node key return current node elif key lt current node key current node current node left else key gt current node key current node current node right return current node Ekleme Eleman ekleme islemi her zaman yapraklara ya da tek cocugu olan dugumlere yapilir Bunun icin oncelikle eklenecek elemanin konumu bulunmalidir konum bulma islemi arama kisminda oldugu gibi buyukse saga kucukse sola ilerle seklinde yapilir Bu algoritma da bir dongu icinde ya da ozyinelemeli sekilde uygulanabilir C kodu su sekildedir Node insert Node amp root int key int value if root root new Node key value else if key lt root gt key root gt left insert root gt left key value else key gt root gt key root gt right insert root gt right key value return root Silme Iki cocugu olan bir dugumun D silinmesi D E ile yer degistirilip siliniyor Silme islemi uc baslik altinda incelenebilir Eger Silinecek dugumun cocugu yoksa basitce dugum silinir Silinecek dugumun tek cocugu varsa dugum silinir ve tek cocuk silinen dugumun yerine tasinir Silinecek dugumun iki cocugu varsa silinecek dugume D diyelim D yi silmeden once D den buyuk en kucuk eleman bulunur inorder successor buna da E diyelim E ile D yer degistirilir ve ardindan D silinir Bir elemandan buyuk en kucuk eleman o elemanin sag alt agacinin en solundaki elemandir ve bunu bulmak icin ekstra metot yazmak gerekir Bu yuzden silme algoritmasi ekleme ve arama algoritmalarina gore daha uzundur Python kodu su sekildedir def find min self Gets minimum node in a subtree current node self while current node left child current node current node left child return current node def replace node in parent self new value None if self parent if self self parent left child self parent left child new value else self parent right child new value if new value new value parent self parent def binary tree delete self key if key lt self key self left child binary tree delete key elif key gt self key self right child binary tree delete key else delete the key here if self left child and self right child if both children are present successor self right child find min self key successor key successor binary tree delete successor key elif self left child if the node has only a left child self replace node in parent self left child elif self right child if the node has only a right child self replace node in parent self right child else this node has no children self replace node in parent None Dengeli ikili arama agaclariBir agactaki tum dugumlerin sag alt agaclari ve sol alt agaclari arasindaki yukseklik farki en fazla 1 ise o agac dengeli olarak tanimlanir Agaclarin dengeli olmasi onlarin yuksekligini azaltarak agac uzerinde calisan algoritmalarin performansini arttirir Ornegin bos bir ikili arama agacina 1 2 3 4 5 6 7 elemanlarini sirayla ekledigimizi dusunelim Bu durumda elemanlar hep sag tarafa eklenecegi icin agac esasen bir bagli listeye donusur Halbuki ayni elemanlar yuksekligi 3 olan bir agaca da yerlestirilebilirlerdi Bu durum dengeli ikili arama agaclarinin icadina yol acmistir AVL agaci ve kirmizi siyah agaclar dengeli agaclara ornektir