Bináris keresőfa adatszerkezete példákkal magyarázva

A fa egy csomópontokból álló adatszerkezet, amely a következő jellemzőkkel rendelkezik:

  1. Minden fának van egy gyökércsomópontja (a tetején), amelynek van valamilyen értéke.
  2. A gyökércsomópontnak nulla vagy több gyermekcsomópontja van.
  3. Minden gyermekcsomópontnak nulla vagy több gyermekcsomópontja van, és így tovább. Ezzel létrejön egy alfa a fában. Minden csomópontnak megvan a maga alfája, amelyet a gyermekei és gyermekei alkotnak stb. Ez azt jelenti, hogy minden csomópont önmagában fa lehet.

A bináris keresési fa (BST) hozzáadja ezt a két jellemzőt:

  1. Minden csomópontban legfeljebb két gyermek van.
  2. Minden csomópontnál a bal leszármazott csomópontok értéke kisebb, mint az aktuális csomópont értéke, ami viszont kisebb, mint a jobb leszármazott csomópontok (ha vannak).

A BST a bináris keresési algoritmus ötletére épül, amely lehetővé teszi a csomópontok gyors megkeresését, beillesztését és eltávolítását. Beállításuk módja azt jelenti, hogy átlagosan minden egyes összehasonlítás lehetővé teszi a műveletek számára a fa kb. Felének átugrását, így minden keresés, beillesztés vagy törlés időt vesz igénybe a fában tárolt elemek számának logaritmusával arányosan, O(log n).

Néha azonban előfordulhat a legrosszabb eset, amikor a fa nincs kiegyensúlyozva, és az idő összetettsége O(n)mindhárom funkcióra vonatkozik. Ezért az önkiegyensúlyozó fák (AVL, vörös-fekete stb.) Sokkal hatékonyabbak, mint az alap BST.

Példa a legrosszabb esetre: Ez akkor fordulhat elő, ha folyamatosan olyan csomópontokat ad hozzá, amelyek mindig nagyobbak, mint az előző csomópont (ez a szülő), ugyanez történhet, ha mindig olyan csomópontokat ad hozzá, amelyek értéke alacsonyabb, mint a szüleiké.

Alapvető műveletek BST-n

  • Create: létrehoz egy üres fát.
  • Beszúrás: csomópont beillesztése a fába.
  • Keresés: Csomópontot keres a fában.
  • Törlés: egy csomópont törlése a fáról.

Teremt

Kezdetben egy üres fa jön létre csomópontok nélkül. A változó / azonosító, amelynek a gyökércsomópontra kell mutatnia, egy NULLértékkel inicializálódik .

Keresés

Mindig elkezdi keresni a fát a gyökércsomópontnál, és onnan megy le. Összehasonlítja az egyes csomópontok adatait a keresettekkel. Ha az összehasonlított csomópont nem egyezik, akkor vagy a jobb vagy a bal gyermek felé halad, ami a következő összehasonlítás eredményétől függ: Ha a keresett csomópont alacsonyabb, mint amellyel összehasonlította, a bal gyermekhez haladsz, különben (ha nagyobb) a jobb gyerekhez lépsz. Miért? Mivel a BST felépítése (definíciójának megfelelően), hogy a jobb gyermek mindig nagyobb, mint a szülő, a bal gyermek pedig mindig kisebb.

Helyezze be

Nagyon hasonlít a keresési funkcióhoz. Ismét a fa gyökeréből indul ki, és rekurzívan megy lefelé, keresve a megfelelő helyet az új csomópont beszúrásához, ugyanúgy, ahogyan azt a keresési funkció ismerteti. Ha az azonos értékű csomópont már benne van a fában, választhatja, hogy beszúrja-e a duplikátumot, vagy sem. Egyes fák megengedik a másolatokat, mások nem. Ez a bizonyos megvalósítástól függ.

Töröl

Három eset fordulhat elő, amikor egy csomópontot próbál törölni. Ha van,

  1. Nincs alfa (nincs gyerek): Ez a legkönnyebb. Egyszerűen csak törölheti a csomópontot, további műveletek nélkül.
  2. Egy alfa (egy gyermek): Meg kell győződnie arról, hogy a csomópont törlése után gyermeke csatlakozik a törölt csomópont szülőihez.
  3. Két részfa (két gyermek): Meg kell találnia és ki kell cserélnie a törölni kívánt csomópontot az utódjával (a legalsó csomópont a jobb részfán).

A fa létrehozásának időbeli összetettsége O(1). A csomópont keresésének, beillesztésének vagy törlésének bonyolultsága a fa magasságától függ h, tehát a legrosszabb eset O(h).

Egy csomópont elődje

Az elődök leírhatók, mint azok a csomópontok, amelyek közvetlenül a csomópont előtt jönnének. Az aktuális csomópont elődjének megtalálásához nézze meg a bal oldali fán a jobb oldali legtöbb / legnagyobb levélcsomópontot.

Egy csomópont utódja

Az utódok leírhatók, mint azok a csomópontok, amelyek közvetlenül a csomópont után jönnének. Az aktuális csomópont utódjának megtalálásához nézze meg a bal oldali / legkisebb levélcsomópontot a jobb alfában.

A BT speciális típusai

  • Halom
  • Vörös-fekete fa
  • B-fa
  • Splay fa
  • N-ary fa
  • Trie (Radix-fa)

Futásidő

Adatszerkezet: tömb

  • Legrosszabb eset: O(log n)
  • Legjobb teljesítmény: O(1)
  • Átlagos teljesítmény: O(log n)
  • A legrosszabb eset bonyolultsága: O(1)

Hol nvan a csomópontok száma a BST-ben.

A BST megvalósítása

Íme a BST csomópont meghatározása, amely rendelkezik néhány adattal, hivatkozva a bal és a jobb gyermek csomópontra.

struct node { int data; struct node *leftChild; struct node *rightChild; };

Keresés művelet

Amikor egy elemet keresni kíván, kezdje el a keresést a gyökércsomóponttól. Ezután, ha az adatok kisebbek, mint a kulcsérték, keresse meg az elemet a bal alfában. Ellenkező esetben keresse meg az elemet a jobb részfában. Kövesse ugyanazt az algoritmust minden csomópontnál.

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; }

Helyezze be a műveletet

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; } } } } } 

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)); }

Relevant videos on freeCodeCamp YouTube channel

  • Binary Search Tree
  • 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