İkili Arama Ağacı nedir?
Ağaç, aşağıdaki özelliklere sahip düğümlerden oluşan bir veri yapısıdır:
- Her ağacın tepesinde bir değer (herhangi bir veri türü olabilir) içeren bir kök düğümü (Ana Düğüm olarak da bilinir) vardır.
- Kök düğümün sıfır veya daha fazla alt düğümü vardır.
- Her çocuk düğümün sıfır veya daha fazla alt düğümü vardır ve bu böyle devam eder. Bu, ağaçta bir alt ağaç oluşturur. Her düğümün çocuklarından ve çocuklarından vb. Oluşan kendi alt ağacı vardır. Bu, her düğümün kendi başına bir ağaç olabileceği anlamına gelir.
İkili arama ağacı (BST) şu iki özelliği ekler:
- Her düğümün en fazla iki çocuğu vardır.
- Her bir düğüm için, sol alt düğümlerinin değerleri, mevcut düğümün değerlerinden daha azdır ve bu da, sağ alt düğümlerden (varsa) daha küçüktür.
BST, düğümlerin hızlı aranmasına, eklenmesine ve kaldırılmasına olanak tanıyan ikili arama algoritması fikri üzerine kurulmuştur. Ayarlanma şekli, ortalama olarak, her bir karşılaştırmanın işlemlerin ağacın yaklaşık yarısını atlamasına izin verdiği anlamına gelir, böylece her arama, ekleme veya silme, ağaçta depolanan öğe sayısının logaritmasıyla orantılı zaman alır, O(log n). Bununla birlikte, bazen en kötü durum, ağaç dengeli olmadığında ve zaman karmaşıklığı O(n) bu üç işlev için de gerçekleşebilir. Bu nedenle kendi kendini dengeleyen ağaçlar (AVL, kırmızı-siyah vb.) Temel BST'den çok daha etkilidir.
En kötü durum senaryosu örneği: Bu, her zaman öncekinden (üst) düğümden daha büyük olan düğümleri eklemeye devam ettiğinizde gerçekleşebilir, aynı şey her zaman üstlerinden daha düşük değerlere sahip düğümler eklediğinizde de olabilir.
Bir BST üzerindeki temel işlemler
- Oluştur: boş bir ağaç oluşturur.
- Ekle: ağaca bir düğüm ekleyin.
- Ara: Ağaçta bir düğüm arar.
- Sil: ağaçtan bir düğümü siler.
- Inorder: Ağacın sıralı geçişi.
- Ön sipariş: ağacın ön siparişi.
- Postorder: ağacın sipariş sonrası geçişi.
Oluşturmak
Başlangıçta herhangi bir düğümü olmayan boş bir ağaç oluşturulur. Kök düğüme işaret etmesi gereken değişken / tanımlayıcı bir NULL değer ile başlatılır .
Arama
Ağacı aramaya her zaman kök düğümde başlarsınız ve oradan aşağı inersiniz. Her düğümdeki verileri aradığınızla karşılaştırırsınız. Karşılaştırılan düğüm eşleşmezse, ya sağ çocuğa ya da soldaki çocuğa ilerlersiniz, bu aşağıdaki karşılaştırmanın sonucuna bağlıdır: Aradığınız düğüm, karşılaştırdığınız düğümden daha düşükse, sol çocuğa ilerlersiniz, aksi takdirde (daha büyükse) sağ çocuğa gidersiniz. Neden? BST yapılandırıldığı için (tanımına göre), sağ çocuk her zaman ebeveynden daha büyük ve sol çocuk her zaman daha küçüktür.
Kapsamlı arama (BFS)
Genişlik ilk arama, bir BST'yi geçmek için kullanılan bir algoritmadır. Kök düğümde başlar ve istenen düğümü arayarak yanal bir şekilde (yan yana) hareket eder. Bu tür arama, her bir düğümün bir kez ziyaret edildiği ve ağacın boyutunun doğrudan aramanın uzunluğu ile ilişkili olduğu göz önüne alındığında O (n) olarak tanımlanabilir.
Önce derinlik arama (DFS)
Derinlik öncelikli arama yaklaşımıyla, kök düğüm ile başlayıp tek bir daldan aşağı iniyoruz. İstenilen düğüm bu dalda bulunursa, harika, ancak değilse, yukarı doğru devam edin ve ziyaret edilmeyen düğümleri arayın. Bu tür aramada ayrıca büyük bir O (n) gösterimi vardır.
Ekle
Arama işlevine çok benzer. Arama işlevinde açıklandığı gibi, yine ağacın kökünden başlar ve yinelemeli olarak aşağı inersiniz, yeni düğümümüzü eklemek için doğru yeri ararsınız. Ağaçta aynı değere sahip bir düğüm varsa, kopyayı ekleyip eklememeyi seçebilirsiniz. Bazı ağaçlar kopyalara izin verirken bazıları izin vermez. Belirli uygulamaya bağlıdır.
Silme
Bir düğümü silmeye çalışırken meydana gelebilecek 3 durum vardır. Varsa,
- Alt ağaç yok (çocuk yok): Bu en kolayı. Herhangi bir ek işlem gerekmeden düğümü kolayca silebilirsiniz.
- Bir alt ağaç (bir çocuk): Düğüm silindikten sonra altının silinen düğümün ebeveynine bağlandığından emin olmalısınız.
- İki alt ağaç (iki alt ağaç): Silmek istediğiniz düğümü, sıralı halefiyle (sağ alt ağaçta en soldaki düğüm) bulmanız ve değiştirmeniz gerekir.
Bir ağaç oluşturmanın zaman karmaşıklığı O(1). Bir düğümü aramak, eklemek veya silmek için zaman karmaşıklığı ağacın yüksekliğine bağlıdır h, bu nedenle en kötü durum O(h) eğimli ağaçlar durumundadır.
Bir düğümün öncülü
Önceller, şu anda bulunduğunuz düğümden hemen önce gelecek olan düğüm olarak tanımlanabilir. Mevcut düğümün öncülünü bulmak için, sol alt ağaçtaki en sağdaki / en büyük yaprak düğüme bakın.
Bir düğümün halefi
Halefler, mevcut düğümden hemen sonra gelecek olan düğüm olarak tanımlanabilir. Geçerli düğümün halefini bulmak için, sağ alt ağaçtaki en soldaki / en küçük yaprak düğümüne bakın.
Özel BT türleri
- Yığın
- Kırmızı-siyah ağaç
- B ağacı
- Splay ağacı
- N-ary ağacı
- Trie (Radix ağacı)
Çalışma süresi
Veri yapısı: BST
- En kötü durum performansı:
O(n) - En iyi durum performansı:
O(1) - Ortalama performans:
O(log n) - En kötü durum alanı karmaşıklığı:
O(1)
n BST'deki düğüm sayısı nerede . En kötü durum O (n) 'dir çünkü BST dengesiz olabilir.
BST'nin uygulanması
Sol ve sağ alt düğümlerine atıfta bulunarak, bazı verilere sahip bir BST düğümünün tanımı.
struct node { int data; struct node *leftChild; struct node *rightChild; }; Arama İşlemi
Bir eleman aranacağı zaman, kök düğümden aramaya başlayın. Ardından, veriler anahtar değerinden düşükse, sol alt ağaçta öğeyi arayın. Aksi takdirde, sağ alt ağaçta öğeyi arayın. Her düğüm için aynı algoritmayı izleyin.
struct node* search(int data){ struct node *current = root; printf("Visiting elements: "); while(current->data != data){ if(current != NULL) { printf("%d ",current->data); //go to left tree if(current->data > data){ current = current->leftChild; }//else go to right tree else { current = current->rightChild; } //not found if(current == NULL){ return NULL; } } } return current; } İşlem Ekle
Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.
void insert(int data) { struct node *tempNode = (struct node*) malloc(sizeof(struct node)); struct node *current; struct node *parent; tempNode->data = data; tempNode->leftChild = NULL; tempNode->rightChild = NULL; //if tree is empty if(root == NULL) { root = tempNode; } else { current = root; parent = NULL; while(1) { parent = current; //go to left of the tree if(data data) { current = current->leftChild; //insert to the left if(current == NULL) { parent->leftChild = tempNode; return; } }//go to right of the tree else { current = current->rightChild; //insert to the right if(current == NULL) { parent->rightChild = tempNode; return; } } } } } Delete Operation
void deleteNode(struct node* root, int data){ if (root == NULL) root=tempnode; if (data key) root->left = deleteNode(root->left, key); else if (key > root->key) root->right = deleteNode(root->right, key); else { if (root->left == NULL) { struct node *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct node *temp = root->left; free(root); return temp; } struct node* temp = minValueNode(root->right); root->key = temp->key; root->right = deleteNode(root->right, temp->key); } return root; } Binary search trees (BSTs) also give us quick access to predecessors and successors. Predecessors can be described as the node that would come right before the node you are currently at.
- To find the predecessor of the current node, look at the rightmost/largest leaf node in the left subtree. Successors can be described as the node that would come right after the node you are currently at.
- To find the successor of the current node, look at the leftmost/smallest leaf node in the right subtree.
Let's look at a couple of procedures operating on trees.
Since trees are recursively defined, it's very common to write routines that operate on trees that are themselves recursive.
So for instance, if we want to calculate the height of a tree, that is the height of a root node, We can go ahead and recursively do that, going through the tree. So we can say:
- For instance, if we have a nil tree, then its height is a 0.
- Otherwise, We're 1 plus the maximum of the left child tree and the right child tree.
- So if we look at a leaf for example, that height would be 1 because the height of the left child is nil, is 0, and the height of the nil right child is also 0. So the max of that is 0, then 1 plus 0.
Height(tree) algorithm
if tree = nil: return 0 return 1 + Max(Height(tree.left),Height(tree.right)) Here is the code in C++
int maxDepth(struct node* node) { if (node==NULL) return 0; else { int rDepth = maxDepth(node->right); int lDepth = maxDepth(node->left); if (lDepth > rDepth) { return(lDepth+1); } else { return(rDepth+1); } } } We could also look at calculating the size of a tree that is the number of nodes.
- Again, if we have a nil tree, we have zero nodes.
- Otherwise, we have the number of nodes in the left child plus 1 for ourselves plus the number of nodes in the right child. So 1 plus the size of the left tree plus the size of the right tree.
Size(tree) algorithm
if tree = nil return 0 return 1 + Size(tree.left) + Size(tree.right) Here is the code in C++
int treeSize(struct node* node) { if (node==NULL) return 0; else return 1+(treeSize(node->left) + treeSize(node->right)); } Traversal
There are 3 kinds of traversals that are done typically over a binary search tree. All these traversals have a somewhat common way of going over the nodes of the tree.
In-order
This traversal first goes over the left subtree of the root node, then accesses the current node, followed by the right subtree of the current node. The code represents the base case too, which says that an empty tree is also a binary search tree.
void inOrder(struct node* root) { // Base case if (root == null) { return; } // Travel the left sub-tree first. inOrder(root.left); // Print the current node value printf("%d ", root.data); // Travel the right sub-tree next. inOrder(root.right); } Pre-order
This traversal first accesses the current node value, then traverses the left and right sub-trees respectively.
void preOrder(struct node* root) { if (root == null) { return; } // Print the current node value printf("%d ", root.data); // Travel the left sub-tree first. preOrder(root.left); // Travel the right sub-tree next. preOrder(root.right); } Post-order
This traversal puts the root value at last, and goes over the left and right sub-trees first. The relative order of the left and right sub-trees remain the same. Only the position of the root changes in all the above mentioned traversals.
void postOrder(struct node* root) { if (root == null) { return; } // Travel the left sub-tree first. postOrder(root.left); // Travel the right sub-tree next. postOrder(root.right); // Print the current node value printf("%d ", root.data); } Relevant videos on freeCodeCamp YouTube channel
And Binary Search Tree: Traversal and Height
Following are common types of Binary Trees:
Full Binary Tree/Strict Binary Tree: A Binary Tree is full or strict if every node has exactly 0 or 2 children.
18 / \ / \ 15 30 / \ / \ 40 50 100 40 In Full Binary Tree, number of leaf nodes is equal to number of internal nodes plus one.
Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible
18 / \ / \ 15 30 / \ / \ 40 50 100 40 / \ / 8 7 9 Perfect Binary Tree A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at the same level.
18 / \ / \ 15 30 / \ / \ 40 50 100 40 Augmenting a BST
Sometimes we need to store some additional information with the traditional data structures to make our tasks easier. For example, consider a scenario where you are supposed to find the ith smallest number in a set. You can use brute force here but we can reduce the complexity of the problem to O(lg n) by augmenting a red-black or any self-balancing tree (where n is the number of elements in the set). We can also compute rank of any element in O(lg n) time. Let us consider a case where we are augmenting a red-black tree to store the additional information needed. Besides the usual attributes, we can store number of internal nodes in the subtree rooted at x(size of the subtree rooted at x including the node itself). Let x be any arbitrary node of a tree.
x.size = x.left.size + x.right.size + 1
While augmenting the tree, we should keep in mind, that we should be able to maintain the augmented information as well as do other operations like insertion, deletion, updating in O(lg n) time.
Since, we know that the value of x.left.size will give us the number of nodes which proceed x in the order traversal of the tree. Thus, x.left.size + 1 is the rank of x within the subtree rooted at x.