İkili arama ağacı - Binary search tree

Kökte 8 olan, 9 boyutunda ve 3 derinliğinde bir ikili arama ağacı. Yapraklar çizilmez.

Gelen bilgisayar bilimleri , bir ikili arama ağacı ( BST ), aynı zamanda bir adlandırılan sipariş veya ikili ağaç sıralanmış bir olduğunu, köklü ikili ağaç veri yapısı olan iç düğümler her mağaza düğümün sol alt ağaçtaki tüm tuşların daha önemli bir büyüktür ve daha az olanlar in daha onun sağ alt ağacı. İkili ağaç, sayılar gibi verileri düzenli bir şekilde depolamak için bir tür veri yapısıdır . İkili arama ağaçları , hızlı arama, veri öğelerinin eklenmesi ve çıkarılması için ikili aramaya izin verir ve dinamik kümeleri ve arama tablolarını uygulamak için kullanılabilir . Bir BST araçlarının düğümlerin emri kalan ağacın yaklaşık yarısını her karşılaştırma atlama, tüm arama alır böylece orantılı zaman ikili logaritma ağacında saklanan öğelerin sayısı. Bu, (sıralanmamış) bir dizideki öğeleri anahtara göre bulmak için gereken doğrusal süreden çok daha iyidir , ancak karma tablolardaki karşılık gelen işlemlerden daha yavaştır . İkili arama ağacının çeşitli varyantları incelenmiştir.

Tanım

İkili arama ağacı, dahili düğümlerinin her biri bir anahtar (ve isteğe bağlı olarak ilişkili bir değer) depolayan ve her birinin, genellikle sol ve sağ olarak gösterilen iki ayırt edici alt ağacı olan köklü bir ikili ağaçtır . Ağaç ayrıca ikili arama özelliğini de karşılar : her düğümdeki anahtar, sol alt ağaçta depolanan herhangi bir anahtardan büyük veya ona eşittir ve sağ alt ağaçta depolanan herhangi bir anahtardan küçük veya ona eşittir. Ağacın yaprakları (son düğümleri) anahtar içermez ve onları birbirinden ayırt edecek bir yapıya sahip değildir.

Çoğu zaman, her bir düğüm tarafından temsil edilen bilgi, tek bir veri öğesinden ziyade bir kayıttır. Bununla birlikte, sıralama amacıyla, düğümler, ilişkili kayıtlarının herhangi bir parçasından ziyade anahtarlarına göre karşılaştırılır. İkili arama ağaçlarının diğer veri yapılarına göre en büyük avantajı, ilgili sıralama algoritmalarının ve sırasız geçiş gibi arama algoritmalarının çok verimli olabilmesidir.

İkili arama ağaçları, kümeler , çoklu kümeler ve ilişkisel diziler gibi daha soyut veri yapıları oluşturmak için kullanılan temel bir veri yapısıdır .

• İkili arama ağacına bir eleman eklerken veya ararken, ziyaret edilen her düğümün anahtarı, eklenecek veya bulunacak elemanın anahtarıyla karşılaştırılmalıdır.
• İkili arama ağacının şekli, tamamen ekleme ve silme sırasına bağlıdır ve dejenere olabilir.
• Rastgele ekleme ve silme uzun karışmış dizisinden sonra ağacın beklenen yüksekliği, anahtarların sayının karekökünü yaklaşır √ n çok daha hızlı daha büyür ki, log n .
• O( n )' nin en kötü durum zaman karmaşıklığına neden olan ağacın dejenerasyonunu önlemek için çok sayıda araştırma yapılmıştır (ayrıntılar için Türler bölümüne bakın ).

sipariş ilişkisi

İkili arama, her öğenin (öğe) toplam ön sipariş anlamında diğer tüm öğelerle karşılaştırılabileceği bir sıra ilişkisi gerektirir . Elemanın karşılaştırmada etkin bir şekilde yer alan kısmına anahtarı denir . Yinelenen olsun, i. e. aynı anahtara sahip farklı elemanlara ağaçta izin verilip verilmeyeceği, sıra ilişkisine değil, altta yatan kümeye, başka bir deyişle: yalnızca uygulamaya bağlı olacaktır. Bir ağaçtaki kopyaları destekleyen ve işleyen bir arama işlevi için , yinelenenlere izin verildiğinde arama bölümüne bakın .

İkili arama ağaçları bağlamında, toplam ön sipariş, en esnek şekilde üç yönlü bir karşılaştırma alt programı aracılığıyla gerçekleştirilir .

Operasyonlar

İkili arama ağaçları üç ana işlemi destekler: arama (bir anahtarın olup olmadığını kontrol etme), bir öğenin eklenmesi ve bir öğenin silinmesi. Son ikisi muhtemelen ağacı değiştirir, ilki ise gezinme ve salt okunur bir işlemdir. Diğer salt okunur işlemler arasında geçiş, doğrulama vb.

Aranıyor

Belirli bir anahtar için ikili arama ağacında arama, yinelemeli veya yinelemeli olarak programlanabilir .

Kök düğümü inceleyerek başlıyoruz . Ağaç null ise , aradığımız anahtar ağaçta yok. Aksi takdirde, anahtar kökünkine eşitse, arama başarılı olur ve düğümü döndürürüz. Anahtar kökünkinden küçükse, sol alt ağaçta arama yaparız. Benzer şekilde, anahtar kökünkinden büyükse, sağ alt ağacı ararız. Bu işlem, anahtar bulunana veya kalan alt ağaç null olana kadar tekrarlanır . Boş bir alt ağaca ulaşıldıktan sonra aranan anahtar bulunamazsa , anahtar ağaçta yoktur. Bu, özyinelemeli bir algoritma olarak kolayca ifade edilir ( Python'da uygulanır ):

def search_recursively(key, node):
    if node is None or key == node.key:
        return node
    if key < node.key:
        return search_recursively(key, node.left)
    return search_recursively(key, node.right)

Aynı algoritma yinelemeli olarak uygulanabilir:

def search_iteratively(key, node):
    while node is not None and node.key != key:
        if key < node.key:
            node = node.left
        else:
            node = node.right
    return node

Arama işlevinin aşağıdaki etkileşimli sürümü, düğüm veri yapısında üst işaretçileri kullanmaz, bunun yerine işaretçileri atalara tutmak için bir yığın kullanır. Bu yığın, travers adı verilen daha büyük bir yapıya gömülüdür.

struct TreeNode {
  struct TreeNode *child[2];
  int key;
  int value;
} Node;

#define LEFT  0
#define RIGHT 1
#define left  child[LEFT]
#define right child[RIGHT]

#define MAXheight 1024 // BST is possibly unbalanced

struct traverser {
  Node*  nod1;  // current position (NULL,
                //   if nod1->key ahead or behind all nodes of bst)
  int    dir;   // ∈ {LEFT,FOUND,RIGHT}, i.e.
                // == LEFT  <==> position at < nod1
                // == FOUND <==> position at   nod1
                // == RIGHT <==> position at > nod1
  Node** parent = &ancestors[0]; // -> parent of nod1 or NULL if root
  // ancestors[0] == trav->bst->root, if tree not empty.
  Node** limit  = &ancestors[MAXheight]; // -> utmost entry
  BST*   bst;   // -> BST to which this traverser belongs
  Node*  ancestors[MAXheight-1];
};

// search Iteratively with Traverser:
int searchIT (struct traverser* trav, int key) {
  assert (trav != NULL && trav->bst != NULL);
  trav->parent = &(trav->ancestors[-1]);
  dir = LEFT; // in case trav->bst (and while-loop) is empty
  node = trav->bst->root;
  while (node != NULL) {
    if (key == node->key) { // key is in the BST
      trav->node = node; // onto trav
      trav->dir = FOUND;
      // 2 == FOUND: key == node->key
      return node;
    }
    if (key < node->key) dir = LEFT;
    else dir = RIGHT;
    if (++(trav->parent) >= limit) { // stack overflow
      fprintf (stderr, "tree too deep\n");
      exit (EXIT_FAILURE);
    }
    *(trav->parent) = node; // onto stack
    node = node->child[dir];
  }; // end of while-loop
  // *(trav->parent) is the node of closest fit
  trav->dir = dir;
  // 0 == LEFT:  key < (*(trav->parent))->key
  // 1 == RIGHT: key > (*(trav->parent))->key
  return NULL;
}

Bu üç örnek, kopyaları desteklemez, yani ağacı tamamen sıralı olarak kabul ederler.

Özyinelemeli algoritmanın kuyruk özyinelemeli olduğu not edilebilir . Kuyruk çağrısı optimizasyonunu destekleyen bir dilde, özyinelemeli ve yinelemeli örnekler eşdeğer programlara derlenecektir.

En kötü durumda, bu algoritma ağacın kökünden kökten en uzaktaki yaprağa kadar arama yapmak zorunda olduğundan, arama işlemi ağacın yüksekliğiyle orantılı olarak zaman alır (bkz. ağaç terminolojisi ). Ortalama olarak, Düğüm anahtarlı ikili arama ağaçları O (log | Düğüm |) yüksekliğine sahiptir. Ancak, en kötü durumda, dengesiz ağaç bağlantılı bir listeye ( dejenere ağaç ) benzediğinde , ikili arama ağaçları O(| Nodes |) yüksekliğine sahip olabilir .

İzin verilen kopyalarla aramaya

Sipariş ilişkisi yalnızca bir toplam ön sipariş ise, işlevselliğin makul bir uzantısı şudur: ayrıca eşitlik durumunda yapraklara kadar arama. Böylece, o ana kadar ağaçtaki tüm kopyaların sağına veya soluna bir kopyanın nereye ekleneceğini belirlemeye (veya kabloyla bağlamaya) izin verir. Yön kabloluysa, sağ ve sol her iki seçenek, push işlemi olarak ekleme kopyası ve pop işlemi olarak silme ile bir yığını destekler .

def search_duplicatesAllowed(key, node):
    new_node = node
    while new_node != None:
        current_node = new_node
        if key < current_node.key:
            dir = 0  # LEFT
        else:  # key >= current_node.key:
            dir = 1  # RIGHT
        new_node = current_node.child[dir]
    return (dir, current_node)

Böyle bir arama işleviyle donatılmış bir ikili ağaç sıralaması kararlı hale gelir .

geçiş

İkili arama ağacı oluşturulduktan sonra, onun elemanları alınabilir inorder tarafından yinelemeli ağaçtaki her düğüm ile bu modeli devam ardından yinelemeli düğümün sağ alt ağacı kateden, düğüm kendisi erişme kök düğümün sol alt ağacı kateden özyinelemeli olarak erişildiği için. Tüm ikili ağaçlarda olduğu gibi, bir ön sipariş geçişi veya sipariş sonrası geçiş gerçekleştirilebilir , ancak ikisinin de ikili arama ağaçları için yararlı olması muhtemel değildir . Bir ikili arama ağacının sıra dışı geçişi her zaman sıralanmış bir düğüm öğeleri listesi (sayılar, dizeler veya diğer karşılaştırılabilir öğeler) ile sonuçlanır.

Python'da sıralı geçiş için kod aşağıda verilmiştir. Ağaçtaki her düğüm için geri aramayı (programcının düğümün değerinde çağırmak istediği, ekrana yazdırma gibi bazı işlevler) arayacaktır.

def inorder_traversal(node, callback):
    if node == None:
        return
    inorder_traversal(node.leftChild, callback)
    callback(node.value)
    inorder_traversal(node.rightChild, callback)

C'de (özyinelemeli) sıra geçişi için kod aşağıda verilmiştir. Bu durumda printfdüğümün tamsayı değerini ekrana yazdırmak için kullanacaktır .

void inorder_traversal(Node *node) {
  if (node == NULL) return;
  inorder_traversal(node->left);
  printf("%i%i ,", node->key, node->value);
  inorder_traversal(node->right);
}

Her düğümü ziyaret ederken her yayı tam olarak iki kez (bir kez aşağı, bir kez yukarı) ziyaret ettiğinden, her ikili ağaç derinliği ilk geçişi 2×( n −1) ∈ O ( n ) zaman gerektirir . Bu algoritma aynı zamanda O( n )'dir , dolayısıyla asimptotik olarak optimaldir .

Geçiş, yinelemeli olarak da uygulanabilir . Belirli uygulamalar için, örneğin daha büyük eşit arama, yaklaşık arama,tek adımlı (yinelemeli) geçiş çok yararlı olabilir. Bu, elbette, geri arama yapısı olmadan uygulanır.

Sonraki veya önceki düğüme ilerleme

Bu işlev, örneğin aranan öğenin konumunun tam olarak yeterince bilinmediği durumlarda yararlıdır. Bir başlangıç ​​noktasına baktıktan sonra, aramaya sırayla devam edilebilir.

Başlatılacak düğüm, bir arama fonksiyonu aracılığıyla BST'de bulunmuş olabilir. Üst işaretçileri kullanmayan aşağıdaki örnekte, atalara yönelik işaretçi yığını, örneğin başarılı sonucu olan bir searchITişlev tarafından oluşturulmuştur .

Fonksiyon inorderNext , bulan bir anket araştırmalarında-komşu döner node, ya inorder- suc Processor (için dir=RIGHT) ya da inorder- prede Processor (için dir=LEFT), ve güncellenmiş stack, bu nedenle ikili arama ağacı sırayla olabileceğini geçilen inorder-ve arandı verilen yön dirdaha ileride.

/* Returns the next or previous data item in inorder within the tree being traversed with trav, or if there are no more data items returns NULL.
In the former case inorderNext() may be called again to retrieve the second next item. */
Node* inorderNext (struct traverser* trav, dir) {
  assert (trav != NULL);
  assert (trav->dir == FOUND);
  assert (dir == LEFT || dir == RIGHT);

  newnode = trav->node->child[dir];
  if (newnode != NULL) {
// Part A: node has a dir-child.
    do {
      node = newnode;
      if (++(trav->parent) > limit) { // stack overflow
        fprintf (stderr, "tree too deep\n");
        exit (EXIT_FAILURE);
      }
      *(trav->parent) = node; // onto stack
      newnode = node->child[1-dir]
    } until (newnode == NULL);
    return node;
  }
// Part B: node does not have a dir-child.
  do {
    if (--(trav->parent) < &(trav->ancestors[0])) // stack is empty
      return NULL;
    oldnode = node;
    node = *(trav->parent); // parent of oldnode
  } until (oldnode != node->child[dir]);
  // now: oldnode == node->child[1-dir], i.e.
  //      node is ancestor (and predecessor for dir==LEFT resp.
  //      successor for dir==RIGHT) of the original trav->node.
  return node;
}

Fonksiyonun tuşları kullanmadığına dikkat edin; bu, sıralı yapının tamamen ikili arama ağacının yayları tarafından kaydedildiği anlamına gelir. Yön değişikliği olmayan geçişler için, ( amorti edilmiş ) ortalama karmaşıklık, tam bir geçişin, yay yukarı için 1 adım ve yay aşağı için 1 boyutlu bir BST için adımlar atmasıdır . En kötü durum karmaşıklığı olduğu ile ağacın yüksekliği olarak. ${\görüntüleme stili {\matematiksel {O}}(1),}$${\ Displaystyle 2n-2}$${\görüntüleme stili n,}$${\görüntüleme stili {\matematiksel {O}}(h)}$${\görüntüleme stili h}$

Uygulama, ağacın yüksekliğiyle orantılı yığın alanı gerektirir.

Doğrulama

Bazen zaten bir ikili ağacımız var ve bunun bir BST olup olmadığını belirlememiz gerekiyor. Bu problemin basit bir özyinelemeli çözümü var.

BST özelliği (sağ alt ağaçtaki her düğüm mevcut düğümden daha büyük olmalı ve sol alt ağaçtaki her düğüm mevcut düğümden daha küçük olmalıdır) bir ağacın BST olup olmadığını anlamanın anahtarıdır. Açgözlü algoritma -sadece düğüm sağ çocuk yok tüm durumlar için çalışmaz üzerinde değerden daha bir değer sol çocuğa değerinden daha büyük ve daha küçük içerip içermediğini her düğüm check, ağaç travers. Aşağıdaki ağacı düşünün:

     20
    /  \
  10    30
       /  \
      5    40

Yukarıdaki ağaçta, her düğüm, düğümün sol alt öğesinden daha büyük ve sağ alt öğesinden daha küçük bir değer içermesi koşulunu karşılar, ancak yine de bir BST değildir: 5 değeri, 20 içeren düğümün sağ alt ağacındadır. , BST mülkünün ihlali.

Yalnızca bir düğümün ve çocuklarının değerlerine dayalı bir karar vermek yerine, ebeveynden aşağı doğru akan bilgilere de ihtiyacımız var. Yukarıdaki ağaç durumunda, 20 değerini içeren düğümü hatırlayabilseydik, 5 değerli düğümün BST mülkiyet sözleşmesini ihlal ettiğini görürdük.

Yani her düğümde kontrol etmemiz gereken koşul:

• düğüm, ebeveyninin sol çocuğuysa, ebeveynden daha küçük (veya ona eşit) olmalıdır ve bu alt ağaçtaki düğümlerden hiçbirinin daha büyük olmadığından emin olmak için ebeveyninden sağ alt ağacına değeri iletmelidir. ebeveynden daha
• düğüm, ebeveyninin sağ çocuğuysa, ebeveynden daha büyük olmalı ve bu alt ağaçtaki hiçbir düğümün ebeveynden daha küçük olmadığından emin olmak için ebeveyninin değerini sol alt ağacına iletmelidir.

C++'da özyinelemeli bir çözüm bunu daha fazla açıklayabilir:

struct TreeNode {
    int key;
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isBST(struct TreeNode *node, int minKey, int maxKey) {
    if (node == NULL) return true;
    if (node->key < minKey || node->key > maxKey) return false;
    
    return isBST(node->left, minKey, node->key−1) && isBST(node->right, node->key+1, maxKey);
}

node->key+1ve node->key−1BST'de yalnızca farklı öğelere izin vermek için yapılır.

Aynı unsurların da mevcut olmasını istiyorsak, sadece node->keyher iki yerde de kullanabiliriz .

Bu işleve yapılan ilk çağrı şöyle olabilir:

if (isBST(root, INT_MIN, INT_MAX)) {
    puts("This is a BST.");
} else {
    puts("This is NOT a BST!");
}

Esasen geçerli bir aralık oluşturmaya devam ediyoruz ([MIN_VALUE, MAX_VALUE]'dan başlayarak) ve özyinelemeli olarak aşağı indikçe her düğüm için onu küçültmeye devam ediyoruz.

#Geçiş bölümünde belirtildiği gibi , bir ikili arama ağacının sıralı olmayan geçişi, sıralanan düğümleri döndürür. Bu nedenle, ağaçta gezinirken yalnızca son ziyaret edilen düğümü tutmamız ve anahtarının mevcut anahtara kıyasla daha küçük (veya ağaçta kopyalara izin veriliyorsa daha küçük/eşit) olup olmadığını kontrol etmemiz gerekir.

sokma

Ekleme, bir aramanın başlayacağı gibi başlar; anahtar kökünkine eşit değilse, daha önce olduğu gibi sol veya sağ alt ağaçları ararız. Sonunda, harici bir düğüme ulaşacağız ve düğümün anahtarına bağlı olarak yeni anahtar/değer çiftini (burada 'newNode' kaydı olarak kodlanmıştır) sağ veya sol çocuğu olarak ekleyeceğiz. Başka bir deyişle, kökü inceler ve anahtarı kökünkinden küçükse sol alt ağaca, anahtarı kökten büyük veya ona eşitse sağ alt ağaca özyinelemeli olarak yeni düğümü ekleriz.

Tipik bir ikili arama ağacı ekleme C++'da bir ikili ağaçta şu şekilde gerçekleştirilebilir :

void insert(Node*& root, int key, int value) {
  if (!root) 
    root = new Node(key, value);
  else if (key == root->key)
    root->value = value;
  else if (key < root->key)
    insert(root->left, key, value);
  else  // key > root->key
    insert(root->right, key, value);
}

Alternatif olarak, C'de bunun gibi özyinelemeli olmayan bir sürüm uygulanabilir . Nereden geldiğimizi takip etmek için bir işaretçiden işarete kullanmak, kodun, ağaç köküne bir düğüm eklemesi gereken durumu açıkça kontrol etmekten ve ele almaktan kaçınmasını sağlar:

void insert(Node** root, int key, int value) {
  Node **walk = root;
  while (*walk) { 
    int curkey = (*walk)->key;
    if (curkey == key) {
      (*walk)->value = value;
      return;
    }
    if (key > curkey) 
      walk = &(*walk)->right;
    else 
      walk = &(*walk)->left;
  }
  *walk = new Node(key, value);
}

Üst işaretçileri kullanmayan aşağıdaki örnekte, atalara yönelik işaretçi yığını, örneğin sonuç anahtarı not olan bir searchITişlev tarafından oluşturulmuştur . node->keyFOUND

// insert after search Iteratively with Traverser:
void insertIT(struct traverser* trav,Node* node) {
  assert (trav != NULL);
  assert (trav->node != NULL);
  assert (trav->dir == LEFT || trav->dir == RIGHT);
  assert (node != NULL);
  trav->node->child[trav->dir] = node;
  if (++(trav->parent) > limit) { // stack overflow
    fprintf (stderr, "tree too deep\n");
    exit (EXIT_FAILURE);
  }
  *(trav->parent) = node; // onto stack
}

Yukarıdaki yıkıcı prosedür varyantı, ağacı yerinde değiştirir. Yalnızca sabit yığın alanı kullanır (ve yinelemeli sürüm de sabit yığın alanı kullanır), ancak ağacın önceki sürümü kaybolur. Alternatif olarak, aşağıdaki Python örneğinde olduğu gibi, eklenen düğümün tüm atalarını yeniden oluşturabiliriz; orijinal ağaç köküne yapılan herhangi bir referans geçerli kalır ve ağacı kalıcı bir veri yapısı haline getirir :

def binary_tree_insert(node, key, value):
    if node == None:
        return NodeTree(None, key, value, None)
    if key == node.key:
        return NodeTree(node.left, key, value, node.right)
    if key < node.key:
        return NodeTree(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
    return NodeTree(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))

Kullanımları yeniden oluşturulur parçası O (log n ) , ortalama durum uzay ve O ( n ) en kötü durumda.

Her iki versiyonda da bu işlem, en kötü durumda ağacın yüksekliğiyle orantılı bir süre gerektirir; bu, tüm ağaçlar için ortalama durumda O(log n ) süresidir, ancak en kötü durumda O( n ) süresidir.

Yerleştirmeyi açıklamanın bir başka yolu, ağaca yeni bir düğüm eklemek için anahtarın önce kökün anahtarıyla karşılaştırılmasıdır. Anahtarı kökünkinden küçükse, kökün sol çocuğunun anahtarıyla karşılaştırılır. Anahtarı daha büyükse, kökün sağ çocuğu ile karşılaştırılır. Bu işlem, yeni düğüm bir yaprak düğümü ile karşılaştırılıncaya kadar devam eder ve daha sonra anahtarına bağlı olarak bu düğümün sağ veya sol çocuğu olarak eklenir: anahtar, yaprağın anahtarından küçükse, yaprağın anahtarı olarak eklenir. sol çocuk, aksi takdirde yaprağın sağ çocuğu.

İkili bir ağaca düğüm eklemenin başka yolları da vardır, ancak yapraklara düğüm eklemenin ve aynı zamanda BST yapısını korumanın tek yolu budur.

silme

İkili arama ağacından bir düğümü çıkarırken , düğümlerin sıralı sırasını korumak zorunludur. Bunu yapmak için birçok olasılık var. Ancak 1962 yılında T. Hibbard tarafından önerilen aşağıdaki yöntem, söz konusu alt ağaçların yüksekliklerinin en fazla bir tane değiştirilmesini garanti etmektedir. Göz önünde bulundurulması gereken üç olası durum vardır:

1. Çocuğu olmayan bir düğümü silme: düğümü ağaçtan kaldırmanız yeterlidir.
2. Bir çocuğu olan bir düğümü silme: düğümü kaldırın ve onun alt öğesiyle değiştirin.
3. İki çocuklu bir D düğümünü silme : D' nin sıralı öncülünü veya sıralı ardıl E'yi seçin (şekle bakın). Bunun yerine silme D , ile anahtar ve değerin üzerine E ‘s. Eğer E çocuğu yok, kaldırmak E önceki ebeveynden G ; eğer D çocuğu olan F , bunun yerini alacak böylece, sağ çocuktur E at G .

İkili bir arama ağacından iki çocuklu bir D düğümünü silme . İlk önce sağ alt ağaçtaki en soldaki düğüm, sıralı ardılı E tanımlanır. Değeri silinen D düğümüne kopyalanır . Sıralama ardılı, en fazla bir çocuğu olduğu için kolayca silinebilir (genel olarak dengesiz durumda bir alt ağaç olabilir).
Aynı yöntem, sıralı öncül C kullanılarak simetrik olarak çalışır .

Her durumda, D kök olduğunda, değiştirme düğümünü yeniden kök yapın.

İki çocuklu düğümlerin (durum 3) silinmesi daha zordur (şekle bakın). D düğümünün sıralı halefi, sağ alt ağacının en soldaki çocuğu, diyelim ki E ve bir düğümün sıralı öncülü, sol alt ağacın en sağdaki çocuğu, diyelim C. Her iki durumda da, böyle bir E veya C düğümünün sol yanıtı olmayacaktır. sağ çocuk, bu nedenle yukarıdaki 1 veya 2 daha basit iki durumdan birine göre silinebilir.

İki alt durumun her örneği için inorder ardılını veya inorder öncülünü tutarlı bir şekilde kullanmak, dengesiz bir ağaca yol açabilir , bu nedenle bazı uygulamalar farklı zamanlarda birini veya diğerini seçer.

Çalışma zamanı analizi: Bu işlem her zaman ağaçtan bir yaprağa geçmese de, bu her zaman bir olasılıktır; bu nedenle en kötü durumda ağacın yüksekliğiyle orantılı bir zaman gerektirir. Düğümün iki çocuğu olsa bile daha fazlasını gerektirmez, çünkü hala tek bir yol izler ve hiçbir düğümü iki kez ziyaret etmez.

def find_min(self):
    """Get 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) -> 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) -> None:
    if key < self.key:
        self.left_child.binary_tree_delete(key)
        return
    if key > self.key:
        self.right_child.binary_tree_delete(key)
        return
    # 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:
        self.replace_node_in_parent(None)  # This node has no children

paralel algoritmalar

İkili arama ağaçları için, birden çok öğe ekleme/silme, diziden yapı oluşturma, belirli bir tahminciyle filtreleme, bir diziye düzleştirme, iki ağacı birleştirme/çıkarma/kesişme vb. dahil olmak üzere paralel algoritmalar da vardır. Bu algoritmalar, birleştirme tabanlı kullanılarak uygulanabilir. birkaç dengeleme şeması kullanarak ağacı dengede tutabilen ağaç algoritmaları ( AVL ağacı , kırmızı-siyah ağaç , ağırlık dengeli ağaç ve treap dahil ).

Uygulama örnekleri

Çeşit

Basit bir sıralama algoritması uygulamak için ikili arama ağacı kullanılabilir . Heapsort'a benzer şekilde , sıralamak istediğimiz tüm değerleri yeni bir sıralı veri yapısına (bu durumda bir ikili arama ağacına) ekler ve ardından sırayla çapraz geçiş yaparız.

En kötü durum zaman build_binary_treeolduğu O ( n ² ) Eğer bir içine o, o zincirleri onları değerlerin sıralı bir liste beslemek -eğer bağlantılı listenin hiçbir sol alt ağaçlar ile. Örneğin build_binary_tree([1, 2, 3, 4, 5]), ağacı verir (1 (2 (3 (4 (5))))).

Basit ikili ağaçlarla bu kusurun üstesinden gelmek için birkaç şema vardır; en yaygın olanı kendi kendini dengeleyen ikili arama ağacıdır . Aynı prosedür böyle bir ağaç kullanılarak yapılırsa, genel en kötü durum süresi O( n log n ) olur ve bu, bir karşılaştırmalı sıralama için asimptotik olarak en uygunudur . Uygulamada, ağaç tabanlı bir sıralama (özellikle düğüm tahsisi için ) için zaman ve uzayda eklenen ek yük, onu statik liste sıralama için yığın sıralama gibi diğer asimptotik olarak en uygun sıralamalardan daha düşük kılar . Öte yandan, listeyi her zaman sıralı tutarken bir listeye zaman içinde öğe ekleyerek artımlı sıralamanın en etkili yöntemlerinden biridir .

Öncelikli kuyruk işlemleri

İkili arama ağaçları öncelik sıraları olarak hizmet edebilir : minimum (veya maksimum) anahtarın aranması ve silinmesinin yanı sıra isteğe bağlı anahtarın eklenmesine izin veren yapılar. Ekleme daha önce açıklandığı gibi çalışır. Find-min , soldaki işaretçileri takip ederek bir yaprağa çarpmadan olabildiğince uzağa gider:

// Precondition: T is not a leaf
function find-min(T):
    while hasLeft(T):
        T ? left(T)
    return key(T)

Find-max benzerdir: mümkün olduğunca doğru işaretçileri takip edin. Sil-min ( max ) sadece minimumu (maksimum) arayabilir, ardından silebilir. Bu şekilde, ekleme ve silme, ikili yığında olduğu gibi logaritmik zaman alır , ancak ikili yığın ve diğer öncelikli kuyruk uygulamalarının aksine, tek bir ağaç find-min , find-max , delete-min öğelerinin tümünü destekleyebilir. ve delete-max'ı aynı anda kullanarak ikili arama ağaçlarını çift ​​uçlu öncelik sıraları olarak uygun hale getirir .

Türler

Birçok ikili arama ağacı türü vardır. AVL ağaçları ve kırmızı-siyah ağaçların her ikisi de kendi kendini dengeleyen ikili arama ağaçlarının biçimleridir . Bir yayvan ağacı otomatik köküne yakın sık erişilen elemanlarını hareket eden bir ikili arama ağacı. Bir de treap ( ağaç yığın ), her düğüm ayrıca (rastgele seçilmiş) öncelik tutan ve üst düğüm onun çocuklarından daha yüksek önceliğe sahiptir. Tango ağaçları , hızlı aramalar için optimize edilmiş ağaçlardır. T-ağaçları , bellek içi veritabanları için yaygın olarak kullanılan, depolama alanı ek yükünü azaltmak için optimize edilmiş ikili arama ağaçlarıdır.

Dejenere ağaç, her bir üst düğüm için yalnızca bir ilişkili alt düğümün bulunduğu bir ağaçtır. Dengesizdir ve en kötü durumda, performans bağlantılı bir listenin performansına düşer. Ekleme düğümü işleviniz yeniden dengelemeyi gerçekleştirmiyorsa, zaten sıralanmış verilerle besleyerek kolayca dejenere bir ağaç oluşturabilirsiniz. Bunun anlamı, bir performans ölçümünde ağacın esasen bağlantılı bir liste veri yapısı gibi davranacağıdır.

Performans karşılaştırmaları

DA Heger (2004), ikili arama ağaçlarının performans karşılaştırmasını sundu. Treap'in en iyi ortalama performansa sahip olduğu, kırmızı-siyah ağacın ise en az sayıda performans varyasyonuna sahip olduğu bulundu.

Optimal ikili arama ağaçları

Ağaç rotasyonları, ağaçta mükemmel veya mükemmele yakın iç dengeyi korumak için ikili ağaçlarda çok yaygın dahili işlemlerdir.

Bir arama ağacı değiştirilecek amaçlanmamıştır ve tam olarak her öğe erişilebilir ne sıklıkta biliniyorsa, bir inşa etmek mümkündür optimum ikili arama ağacı , bir arama ağacı, nerede bir öğe ararken ortalama maliyeti ( beklenen search maliyeti ) en aza indirilir.

Yalnızca arama maliyetlerine ilişkin tahminlerimiz olsa bile, böyle bir sistem aramaları ortalama olarak önemli ölçüde hızlandırabilir. Biz kullanılan İngilizce kelimelerin bir BST varsa Örneğin, yazım denetleyicisi , biz de kelime sıklığı dayalı ağaç dengelemek olabilir metin külliyatında gibi kelimeler yerleştirerek gibi kökü ve kelimelerin yakın agerasia yaprakları yakın. Böyle bir ağaç , benzer şekilde yoğun bir bilgi kodlaması üretmek için sık kullanılan öğeleri kökün yanına yerleştirmeye çalışan Huffman ağaçlarıyla karşılaştırılabilir ; ancak, Huffman ağaçları veri öğelerini yalnızca yapraklarda depolar ve bu öğelerin sıralanması gerekmez.

Ağaçtaki öğelere erişilecek dizi önceden bilinmiyorsa, herhangi bir özel arama işlemi dizisi için oluşturabileceğimiz herhangi bir statik arama ağacı kadar asimptotik olarak iyi olan yayılma ağaçları kullanılabilir.

Alfabetik ağaçlar , sıraya göre ek kısıtlamaya sahip Huffman ağaçlarıdır veya eşdeğer olarak, tüm öğelerin yapraklarda depolandığı modifikasyonu olan arama ağaçlarıdır. Optimum alfabetik ikili ağaçlar (OABT'ler) için daha hızlı algoritmalar mevcuttur .

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

•  Bu makale  ,  NIST belgesindeki kamu malı materyali içermektedir :  Black, Paul E. "İkili Arama Ağacı" . Algoritmalar ve Veri Yapıları Sözlüğü .
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. ; Stein, Clifford (2001). "12: İkili arama ağaçları, 15.5: Optimal ikili arama ağaçları". Algoritmalara Giriş (2. baskı). MIT Press ve McGraw-Hill. s. 253–272, 356–363. ISBN'si 0-262-03293-7.
• Jarc, Duane J. (3 Aralık 2005). "İkili Ağaç Geçişleri" . Etkileşimli Veri Yapısı Görselleştirmeleri . Maryland Üniversitesi . Arşivlenmiş orijinal 27 Şubat 2014 tarihinde . Erişim tarihi: 30 Nisan 2006 .
• Knuth, Donald (1997). "6.2.2: İkili Ağaç Arama". Bilgisayar Programlama Sanatı . 3: "Sıralama ve Arama" (3. baskı). Addison-Wesley. s. 426–458. ISBN'si 0-201-89685-0.
• Uzun, Sean. "İkili Arama Ağacı" ( PPT ) . Veri Yapıları ve Algoritmalar Görselleştirme-Bir PowerPoint Slaytlarına Dayalı Yaklaşım . SUNY Oneonta .
• Parlante, Nick (2001). "İkili Ağaçlar" . CS Eğitim Kitaplığı . Stanford Üniversitesi .

Dış bağlantılar

• Ben Pfaff: İkili Arama Ağaçlarına ve Dengeli Ağaçlara Giriş . (PDF; 1675 kB) 2004.
• Binary Tree Visualizer (çeşitli BT tabanlı veri yapılarının JavaScript animasyonu)