Binary Tree

Giriş
std::map veriyapısı binary tree olduğu için O(log(n)) 'dir. Bir binary tree'nin yüksekliği log2(N)+1 'dir. Java'da ise aynı yapı TreeMap'tir.

Optimizasyon
Binary Tree verimli olsa bile daha da optimize edilebilir.
Elimizde şöyle bir ağaç olsun. Her değer ve arama sıklığı tabloda belirtili.

      13                          Key       | 13 | 11 | 26 | 1 | 12 | 28
     /    \                        -----------------------------------------
   11      26                     Frequency | 26 |  5 | 25 | 1 |  3 | 15
  /  \      \                                                 
 1   12      28                                              

Bu ağacın maliyeti şöyledir. Çarpma işlemindeki ikinci sayı değerin derinliğidir. Örneğin 13'ün derinliği 1, 11'in derinliği 2'dir.

26*1 + 5*2 + 25*2 + 1*3 + 3*3 + 15*3.

Eğer ağacı şu hale getirirsek maliyeti daha düşük bir ağaç elde ederiz.

        26
       /  \
      13   28
     /
    11
   /  \
  1    12

Tanımlama
Örnek
Kendi içinde Node sınıfı içeren bir ağacı C# ile kodlamak için şöyle yaparız.

public class BinaryTree<T> where T : IComparable<T>, new()

Eleman Ekleme

Örnek
Recursive yapmak için şöyle yaparız.

typedef struct node{
    int key;
    node *right;
    node *left;
}*nodePtr;

nodePtr root = NULL // As global variable.

void addElement(int key){
  if(root!=NULL){
    if(root->key > key){
      if(root->left!=NULL)
        addElement(key, root->left);
      else
        root->left = createLeaf(key);
      }
    else if(root->key < key){
      if(root->right!=NULL)
        addElement(key, root->right);
      else
        root->right = createLeaf(key);
      }
  }else if(root==NULL)
    root = createLeaf(key);
}

Örnek
Recursive yapmak için şöyle yaparız.

void Bst::_insert(std::unique_ptr<node>& curr, int val)
{
  if (!curr)
  {
    curr = std::make_unique<node>(val);
    return;
  }

  if (val < curr->val)
  {
     _insert(curr->left, val);
  }
  else
  {
    _insert(curr->right, val);
  }
}

Şöyle yaparız

void insert(int val)
{ 
  _insert(root, val);
}

Delete Max
Binary Tree'deki en büyük eleman en sağdaki elemandır. Bunu silmek için şöyle yaparız.

int maxExtract(node **tree)
{
  node *prev = NULL;
  node *curr = *tree;
  int ret;

  if(curr == NULL)
  {
    printf("Tree is empty!\n");
    exit(-1);
  }
  while( curr->right != NULL )
  {
    prev = curr;
    curr = curr->right;
  }

  ret = curr->data;
  if( prev != NULL )
    prev->right = curr->left;
  else if( curr == *tree ) //if the max node ends up being the root.
    *tree = curr->left;
  free(curr);
  return ret;
} 

if the max node ends up being the root. açıklmasının şekli şöyle

    MAX
    /
   x
  / \
A1   A2

MAX silinince elimize şu geçer.

   x
  / \
A1   A2

Silme İşleminde Successor
Silme işleminde ağacı dengeli hale getirme AVLağacı olmasına yardım eder. Şöyledir. Silinecek elemandan sonraki en küçük düğüm bulunur. Bu düğüm sağdaki elemanların en solunda olandır.

private Node getSuccessor(Node delNode){
  Node successorParent = delNode;
  Node successor = delNode;
  Node current = delNode.rightChild;

  while(current != null){
    successorParent = successor;
    successor = current;
    current = current.leftChild;
  } // end of if

  if(successor != delNode.rightChild){
    successorParent.leftChild = successor.rightChild;
    successor.rightChild = delNode.rightChild;
  }
  return successor;

}

Bu düğüm silinecek elemanın yerine getirilir. Getirilmeden önce sağdaki salkımda ufak bir düzenleme yapılır.
Örnek
Silinecek eleman X ise Y direk X ile yer değişir.

X
 \
  Y
   \
    Z

Örnek
Eğer durum şöyle ise

X
 \
  A
 / \
Y   C
 \
  B

Düzenleme ile Y yukarı alınır. Daha sonra X ile Y yer değişir.

X
 \
  Y
   \
    A
   / \
  B   C

Örnek
Silinecek eleman 3 ise 6'lı salkım çıkarılır ve silmeye hazır hale getirilir (3. şekil) Daha sonra 3 ile 4 yer değişir.

      9                                                9
     / \                                              / \
    3  ...                        4                  4  ...
   / \                             \                / \
  2   6              6              6              2   6
 /   / \            / \            / \            /   / \
1   4   7          4   7          5   7          1   5   7
     \   \          \   \              \                  \
      5   8          5   8              8                  8

Örnek
Silinecek elemandan bir sonraki eleman direk sağdaki çocuk ise 3 ve 4 yer değişir.

      8                                 8
     / \                               / \
    3  ...                            4  ...
   / \                               / \
  2   4              4              2   6
 /     \              \            /   / \
1       6              6          1   5   7
       / \            / \         
      5   7          5   7        

Karşılaştırma
Şöyle yaparız.

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
 }

class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {

  if  ( p == null && q==null)
    return true;

  if (p == null || q == null) 
    return false;

  if ( (p.val == q.val) && isSameTree(p.left, q.left) && 
    isSameTree(p.right, q.right))
      return true;
  else 
    return false;  
  }   
}

Tamamen Temizleme
Şöyle yaparız.

// Clears everything out of this binary-tree.
public void Clear()
{
  parentNode = new Node<T>();
}