Binært søketre - Binary search tree

Binært søketre
Binært søketre
Type	tre
Oppfunnet	1960
Oppfunnet av	PF Windley, AD Booth , AJT Colin og TN Hibbard
Tidskompleksitet i stor O -notasjon
Algoritme
Algoritme
Rom
Søk
Sett inn
Slett

Et binært søketre av størrelse 9 og dybde 3, med 8 ved roten. Bladene er ikke tegnet.

I informatikk er et binært søketre ( BST ), også kalt et ordnet eller sortert binært tre , en forankret binær tre datastruktur hvis interne noder hver lagrer en nøkkel større enn alle nøklene i nodens venstre undertre og mindre enn de i det riktige undertreet. Et binært tre er en type datastruktur for lagring av data som tall på en organisert måte. Binære søketrær tillater binært søk etter raskt oppslag, tillegg og fjerning av dataelementer, og kan brukes til å implementere dynamiske sett og oppslagstabeller . Noderekkefølgen i en BST betyr at hver sammenligning hopper over omtrent halvparten av det gjenværende treet, så hele oppslaget tar tid proporsjonalt med den binære logaritmen til antall elementer som er lagret i treet. Dette er mye bedre enn den lineære tiden som kreves for å finne elementer etter nøkkel i en (usortert) matrise, men tregere enn de tilsvarende operasjonene på hashtabeller . Flere varianter av det binære søketreet har blitt studert.

Definisjon

Et binært søketre er et forankret binært tre , hvis interne noder hver lagrer en nøkkel (og eventuelt en tilhørende verdi), og hver har to kjente undertrær, vanligvis betegnet til venstre og høyre . Treet tilfredsstiller i tillegg den binære søkeegenskapen: nøkkelen i hver node er større enn eller lik en nøkkel som er lagret i det venstre undertreet, og mindre enn eller lik en hvilken som helst nøkkel som er lagret i det høyre undertreet. Bladene (siste noder) på treet inneholder ingen nøkkel og har ingen struktur for å skille dem fra hverandre.

Ofte er informasjonen representert av hver node en post i stedet for et enkelt dataelement. For sekvenseringsformål sammenlignes imidlertid noder i henhold til nøklene i stedet for noen del av de tilhørende postene. Den store fordelen med binære søketrær fremfor andre datastrukturer er at de relaterte sorteringsalgoritmene og søkealgoritmene som inorder traversal kan være svært effektive.

Binære søketrær er en grunnleggende datastruktur som brukes til å konstruere mer abstrakte datastrukturer som sett , multisett og assosiative matriser .

Når du setter inn eller søker etter et element i et binært søketre, må nøkkelen til hver besøkte node sammenlignes med nøkkelen til elementet som skal settes inn eller finnes.
Formen på det binære søketreet avhenger helt av rekkefølgen for innsetting og sletting og kan bli degenerert.
Etter en lang blandet sekvens av tilfeldig innsetting og sletting, nærmer den forventede høyden på treet seg kvadratroten av antall nøkler, $\sqrt n$ , som vokser mye raskere enn $log n$ .
Det har vært mye forskning for å forhindre degenerering av treet, noe som resulterer i kompleksitetstid for $O (n)$ i verste fall (for detaljer se avsnitt Typer ).

Ordreforhold

Binært søk krever et ordrerelasjon der hvert element (element) kan sammenlignes med hvert annet element i betydningen en total forhåndsbestilling . Den delen av elementet som effektivt finner sted i sammenligningen kalles dens nøkkel . Enten duplikater, dvs. e. forskjellige elementer med samme nøkkel, skal være tillatt i treet eller ikke, avhenger ikke av ordreforholdet, men av det underliggende settet, med andre ord: bare av applikasjonen. For en søkefunksjon som støtter og håndterer duplikater i et tre, se avsnittet Søke med dubletter tillatt .

I sammenheng med binære søketrær, en total forhåndsbestilling realisert mest fleksibelt ved hjelp av en tre-veis sammenligning subrutine .

Operasjoner

Binære søketrær støtter tre hovedoperasjoner: oppslag (kontroll av om en nøkkel er tilstede), innsetting av et element og sletting av et element. De to sistnevnte endrer muligens treet, mens det første er en navigerings- og skrivebeskyttet operasjon. Andre skrivebeskyttede operasjoner er traversal, verifisering etc.

Søker

Å søke i et binært søketre etter en bestemt nøkkel kan programmeres rekursivt eller iterativt .

Vi begynner med å undersøke rotnoden . Hvis treet er null , finnes ikke nøkkelen vi søker etter i treet. Ellers, hvis nøkkelen er lik roten, er søket vellykket, og vi returnerer noden. Hvis nøkkelen er mindre enn roten, søker vi i venstre undertre. På samme måte, hvis nøkkelen er større enn roten, søker vi etter det riktige undertreet. Denne prosessen gjentas til nøkkelen er funnet eller det gjenværende undertreet er null . Hvis søkte nøkkelen er ikke funnet etter en null treet er nådd, så nøkkelen er ikke til stede i treet. Dette uttrykkes lett som en rekursiv algoritme (implementert i Python ):

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)

Den samme algoritmen kan implementeres iterativt:

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

Følgende interaktive versjon av søkefunksjonen bruker ikke overordnede pekere i nodedatastrukturen, i stedet bruker den en stabel for å holde pekene til forfedrene. Denne bunken er innebygd i en større struktur, kalt traverser.

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

Disse tre eksemplene støtter ikke duplikater, det vil si at de anser treet som fullstendig bestilt.

Man kan merke seg at den rekursive algoritmen er hale rekursiv . I et språk som støtter optimalisering av halen, vil de rekursive og iterative eksemplene kompilere til tilsvarende programmer.

Fordi i verste fall denne algoritmen må søke fra roten til treet til bladet lengst fra roten, tar søkeoperasjonen tid som er proporsjonal med treets høyde (se treterminologi ). I gjennomsnitt har binære søketrær med $Nodes$ -taster $O (logg | Noder |)$ høyde. Imidlertid kan binære søketrær i verste fall ha $O (| Noder |)$ høyde, når det ubalanserte treet ligner en koblet liste ( degenerert tre ).

Søk med dubletter tillatt

Hvis bestillingsforholdet bare er en total forhåndsbestilling, er en rimelig forlengelse av funksjonaliteten følgende: også ved likhetssøk ned til bladene. Dermed tillater du å spesifisere (eller hardtråd) en retning, hvor du skal sette inn en duplikat, enten til høyre eller venstre for alle duplikater i treet så langt. Hvis retningen er fastkoblet, støtter begge valg, høyre og venstre, en bunke med innlegg duplikat som push-operasjon og slett som pop-operasjon.

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)

En binær tresorting utstyrt med en slik søkefunksjon blir stabil .

Traversal

Når det binære søketreet er opprettet, kan elementene hentes i rekkefølge ved rekursivt å krysse venstre undertre av rotnoden, få tilgang til selve noden og deretter rekursivt krysse det høyre undertreet av noden, fortsette dette mønsteret med hver node i treet som det er rekursivt tilgjengelig. Som med alle binære trær, kan man gjennomføre en pre-order traversering eller en post-order traversering , men heller ikke er sannsynlig å være nyttig for binære søketrær. En ordreoverføring av et binært søketre vil alltid resultere i en sortert liste over nodeelementer (tall, strenger eller andre sammenlignbare elementer).

Kode for inorder traversal i Python er gitt nedenfor. Det vil kalle tilbakeringing (noen funksjon programmerer ønsker å ringe på nodens verdi, for eksempel utskrift til skjermen) for hver node i treet.

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

Kode for (rekursiv) inorder traversal i C er gitt nedenfor. I dette tilfellet vil den bruke printftil å skrive ut heltallverdien til noden på skjermen.

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

Hver form for binær tredybde første traversal krever $2 \times (n -1) \in O (n)$ tid, siden den besøker hver bue nøyaktig to ganger (en gang ned, en gang opp) mens du besøker hver node. Denne algoritmen er også $O (n)$ , så den er asymptotisk optimal .

Traversal kan også implementeres iterativt . For visse applikasjoner, f.eks. Større like søk, tilnærmet søk, en operasjon forenkelt trinn (iterativ) traversal kan være veldig nyttig. Dette er selvfølgelig implementert uten tilbakeringingskonstruksjonen.

Gå videre til neste eller forrige node

Denne funksjonen er nyttig f.eks. I tilfeller der plasseringen av elementet det søkes etter ikke er kjent nøyaktig nok. Etter å ha slått opp et utgangspunkt, kan søket fortsette sekvensielt.

Noden som skal startes med kan ha blitt funnet i BST ved hjelp av en søkefunksjon. I det følgende eksemplet, som ikke bruker foreldrepekere, har stabelen med pekere til forfedrene blitt bygget f.eks. Av en searchITfunksjon med vellykket utfall.

Funksjonen inorderNext returnerer en inorder-nabo som ble funnet node, enten inorder- suc 'etterfølger (for dir=RIGHT) eller inorder- prede ' etterfølger (for dir=LEFT), og den oppdaterte stack, slik at det binære søketre kan være sekvensielt inorder-krysset og søkte i gitt retning dirvidere.

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

Vær oppmerksom på at funksjonen ikke bruker taster, noe som betyr at den sekvensielle strukturen er fullstendig registrert av det binære søketreets buer. For traversals uten retningsendring er ( amortisert ) gjennomsnittlig kompleksitet fordi en full traversal tar skritt for en BST av størrelse 1 trinn for bue opp og 1 for bue ned. Den verste tilfellet er med treets høyde. ${\ displaystyle {\ mathcal {O}} (1),}$ ${\ displaystyle 2n-2}$ ${\ displaystyle n,}$ ${\ displaystyle {\ mathcal {O}} (h)}$ ${\ displaystyle h}$

Implementeringen krever stabelplass proporsjonal med høyden på treet.

Bekreftelse

Noen ganger har vi allerede et binært tre, og vi må avgjøre om det er et BST. Dette problemet har en enkel rekursiv løsning.

BST -egenskapen - hver node på høyre undertre må være større enn den nåværende noden, og hver node på venstre undertre må være mindre enn den nåværende noden - er nøkkelen til å finne ut om et tre er en BST eller ikke. Den grådige algoritmen - bare å krysse treet, ved hver node kontrollere om noden inneholder en verdi som er større enn verdien til venstre barn og mindre enn verdien på det riktige barnet - fungerer ikke i alle tilfeller. Tenk på følgende tre:

I treet ovenfor oppfyller hver node betingelsen om at noden inneholder en verdi som er større enn det venstre barnet og mindre enn det høyre barnet holder, og likevel er det ikke en BST: verdien 5 er på høyre undertre av noden som inneholder 20 , brudd på BST -eiendommen.

I stedet for å ta en beslutning utelukkende basert på verdiene til en node og dens barn, trenger vi også informasjon som strømmer ned fra foreldren. Når det gjelder treet ovenfor, hvis vi kunne huske om noden som inneholdt verdien 20, ville vi se at noden med verdi 5 bryter BST -eiendomskontrakten.

Så tilstanden vi må sjekke på hver node er:

hvis noden er venstre barn av sin overordnede, må den være mindre enn (eller lik) overordnet, og den må videresende verdien fra sin overordnede til sitt høyre undertre for å sikre at ingen av nodene i det undertreet er større enn forelder
hvis noden er det riktige barnet til sin overordnede, må den være større enn den overordnede, og den må videresende verdien fra overordnet til venstre undertre for å sikre at ingen av nodene i det undertreet er mindre enn overordnet.

En rekursiv løsning i C ++ kan forklare dette ytterligere:

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+1og node->key−1gjøres for å tillate bare forskjellige elementer i BST.

Hvis vi vil at de samme elementene også skal være tilstede, kan vi bare bruke node->keybegge steder.

Den første samtalen til denne funksjonen kan være omtrent slik:

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

I hovedsak fortsetter vi å lage et gyldig område (fra [MIN_VALUE, MAX_VALUE]) og fortsetter å krympe det for hver node når vi går ned rekursivt.

Som påpekt i avsnitt #traversal , en inorder traversering av et binært søk treet returnerer nodene sortert. Dermed trenger vi bare å beholde den sist besøkte noden mens vi krysser treet og sjekker om nøkkelen er mindre (eller mindre/lik, hvis dubletter skal tillates i treet) sammenlignet med gjeldende nøkkel.

Innsetting

Innsetting begynner som et søk ville begynne; hvis nøkkelen ikke er lik roten, søker vi i venstre eller høyre undertrær som før. Til slutt når vi en ekstern node og legger til det nye nøkkelverdiparet (her kodet som en post 'newNode') som sitt høyre eller venstre barn, avhengig av nodens nøkkel. Med andre ord undersøker vi roten og setter den nye noden rekursivt inn i venstre undertre hvis nøkkelen er mindre enn roten, eller det høyre undertreet hvis nøkkelen er større enn eller lik roten.

Her er hvordan en typisk binær søketreinnsetting kan utføres i et binært tre i C ++ :

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

Alternativt kan en ikke-rekursiv versjon implementeres i C som denne. Ved å bruke en peker-til-peker for å holde oversikt over hvor vi kom fra, kan koden unngå eksplisitt kontroll av og håndtering av saken der den trenger å sette inn en node ved treroten:

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

I det følgende eksemplet, som ikke bruker overordnede pekere, har stabelen med pekere til forfedrene blitt bygd f.eks. Av en searchITfunksjon med utfallstasten node->keyikke FOUND.

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

Den ovennevnte destruktive prosessvarianten endrer treet på plass. Den bruker bare konstant haugplass (og den iterative versjonen bruker også konstant stabelplass), men den tidligere versjonen av treet er tapt. Alternativt, som i følgende Python -eksempel, kan vi rekonstruere alle forfedre til den innsatte noden; enhver referanse til den opprinnelige treroten forblir gyldig, noe som gjør treet til en vedvarende datastruktur :

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

Delen som gjenoppbygges bruker $O (log n)$ plass i gjennomsnittet og $O (n)$ i verste fall.

I begge versjoner krever denne operasjonen tid som er proporsjonal med treets høyde i verste fall, som er $O (log n)$ tid i gjennomsnittlig tilfelle over alle trær, men $O (n)$ tid i verste fall.

En annen måte å forklare innsetting er at for å sette inn en ny node i treet, blir nøkkelen først sammenlignet med roten. Hvis nøkkelen er mindre enn roten, blir den deretter sammenlignet med nøkkelen til rotens venstre barn. Hvis nøkkelen er større, sammenlignes den med rotens riktige barn. Denne prosessen fortsetter, helt til den nye noden sammenlignes med en bladnode, og deretter legges den til som denne nodens høyre eller venstre barn, avhengig av nøkkelen: hvis nøkkelen er mindre enn bladets nøkkel, settes den inn som bladets venstre barn, ellers som bladets høyre barn.

Det er andre måter å sette inn noder i et binært tre, men dette er den eneste måten å sette inn noder på bladene og samtidig bevare BST -strukturen.

Sletting

Ved fjerning av en node fra en binær søke tre er det obligatorisk å opprettholde den inorder sekvens av nodene. Det er mange muligheter for å gjøre dette. Imidlertid garanterer den følgende metoden som ble foreslått av T. Hibbard i 1962 at høyden til emnet subtrees er høyst endret. Det er tre mulige saker å vurdere:

Slette en node uten barn: Bare fjern noden fra treet.
Slette en node med ett barn: Fjern noden og erstatt den med barnet.
Slette en node D med to barn: velge enten D ‘s inorder forgjenger eller inorder etterfølger E (se figur). I stedet for å slette D , skrive sin nøkkel og verdi med E ‘s. Hvis E ikke har et barn, fjern E fra sin forrige overordnede G ; Hvis E har et barn F , er det en rettighet barnet, slik at det er å erstatte E på G .

Sletter en node D med to barn fra et binært søketre. Først identifiseres noden lengst til venstre i høyre undertre, inorder -etterfølgeren E. Verdien kopieres til noden D som slettes. Inorder -etterfølgeren kan deretter enkelt slettes fordi den har høyst ett barn (som i det generelle ubalanserte tilfellet kan være et undertre).
Den samme metoden fungerer symmetrisk ved hjelp av inorder forgjenger C .

I alle tilfeller, når D tilfeldigvis er roten, må du erstatte noden roten igjen.

Noder med to barn (sak 3) er vanskeligere å slette (se figur). En node D’ s inorder -etterfølger er det høyre undertreets barn til venstre, si E , og nodeens forrige forgjenger er venstre undertreets høyre barn, sier C. I begge tilfeller vil en slik node E eller C ikke ha venstre resp. riktig barn, så det kan slettes i henhold til en av de to enklere sakene 1 eller 2 ovenfor.

Konsekvent bruk av inorder-etterfølgeren eller inorder-forgjengeren for hver forekomst av tobarnssaken kan føre til et ubalansert tre, så noen implementeringer velger den ene eller den andre på forskjellige tidspunkter.

Kjøretidsanalyse: Selv om denne operasjonen ikke alltid krysser treet ned til et blad, er dette alltid en mulighet; dermed krever det i verste fall tid proporsjonalt med treets høyde. Det krever ikke mer, selv når noden har to barn, siden den fortsatt følger en enkelt vei og ikke besøker noen node to ganger.

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

Parallelle algoritmer

Det er også parallelle algoritmer for binære søketrær, inkludert innsetting/sletting av flere elementer, konstruksjon fra matrise, filtrering med en bestemt predikator, flat til en matrise, sammenslåing/subtraksjon/skjæring av to trær, etc. Disse algoritmene kan implementeres ved hjelp av join-baserte trealgoritmer , som også kan holde treet balansert ved hjelp av flere balanseringsopplegg (inkludert AVL-tre , rød-svart tre , vektbalansert tre og treap ).

Eksempler på applikasjoner

Sortere

Et binært søketre kan brukes til å implementere en enkel sorteringsalgoritme . I likhet med heapsort setter vi inn alle verdiene vi ønsker å sortere i en ny ordnet datastruktur - i dette tilfellet et binært søketre - og krysser det deretter i rekkefølge.

Den verste tiden build_binary_treeer $O (n 2)$ -hvis du mater den med en sortert liste med verdier, kjeder den dem inn i en sammenkoblet liste uten noen undertrær. For eksempel build_binary_tree([1, 2, 3, 4, 5])gir treet (1 (2 (3 (4 (5))))).

Det er flere ordninger for å overvinne denne feilen med enkle binære trær; det vanligste er det selvbalanserende binære søketreet . Hvis den samme prosedyren utføres ved hjelp av et slikt tre, er den generelle tiden i verste fall $O (n log n)$ , som er asymptotisk optimal for en sammenligningssortering . I praksis er det lagt overhead i tid og rom for en tre-basert slag (særlig for node allokering ) gjør det underlegen andre asymptotisk optimale former slik som heapsort for statisk liste sortering. På den annen side er det en av de mest effektive metodene for inkrementell sortering , og legger elementer til en liste over tid, mens listen holdes sortert til enhver tid.

Prioriterte køoperasjoner

Binære søketrær kan tjene som prioritetskøer : strukturer som tillater innsetting av vilkårlig nøkkel, samt oppslag og sletting av minimumsnøkkel (eller maksimum). Innsetting fungerer som tidligere forklart. Find-min går på treet og følger venstre peker så langt det kan uten å slå et blad:

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

Find-max er analogt: følg riktige tips så langt som mulig. Slett-min ( maks ) kan ganske enkelt slå opp minimum (maksimum) og deretter slette det. På denne måten tar innsetting og sletting både logaritmisk tid, akkurat som de gjør i en binær haug , men i motsetning til en binær haug og de fleste andre prioritetskøimplementeringer, kan et enkelt tre støtte alle finn-min , find-max , delete-min og delete-max samtidig, noe som gjør binære søketrær egnet som dobbeltsidige prioritetskøer .

Typer

Det er mange typer binære søketrær. AVL-trær og rød-svarte trær er begge former for selvbalanserende binære søketrær . Et splay -tre er et binært søketre som automatisk flytter ofte tilgjengelige elementer nærmere roten. I en treap ( tre haug ), hvor hver node har også en (vilkårlig valgt) prioritet og foreldrenoden har høyere prioritet enn sine barn. Tangotrær er trær optimalisert for raske søk. T-trær er binære søketrær optimalisert for å redusere lagringsplass overhead, mye brukt for in-memory databaser

Et degenerert tre er et tre hvor det for hver overordnede node bare er én tilknyttet barnnode. Det er ubalansert og i verste fall forringes ytelsen til en koblet liste. Hvis add-node-funksjonen ikke håndterer ombalansering, kan du enkelt konstruere et degenerert tre ved å mate det med data som allerede er sortert. Hva dette betyr er at i en ytelsesmåling vil treet i hovedsak oppføre seg som en koblet liste datastruktur.

Ytelse sammenligninger

DA Heger (2004) presenterte en ytelses sammenligning av binære søketrær. Det ble funnet at Treap hadde den beste gjennomsnittlige ytelsen, mens rød -svart tre viste seg å ha det minste antallet ytelsesvariasjoner.

Optimale binære søketrær

Trerotasjoner er svært vanlige interne operasjoner i binære trær for å beholde perfekt, eller nesten perfekt, indre balanse i treet.

Hvis et søketre ikke er ment å bli modifisert, og det er nøyaktig kjent hvor ofte hvert element vil nås, er det mulig å konstruere et optimalt binært søketre , som er et søketre hvor gjennomsnittskostnaden for å slå opp et element ( den forventede søkekostnaden ) er minimert.

Selv om vi bare har estimater av søkekostnadene, kan et slikt system i gjennomsnitt øke hastigheten på oppslag. For eksempel, hvis vi har en BST av engelske ord som brukes i en stavekontroll , kan vi balansere treet basert på ordet frekvens i tekstkorpus , plassere ord som den nær roten og ord som agerasia nær bladene. Et slikt tre kan sammenlignes med Huffman -trær , som på samme måte søker å plassere ofte brukte gjenstander nær roten for å produsere en tett informasjonskoding; Huffman -trær lagrer imidlertid dataelementer bare i blader, og disse elementene trenger ikke bestilles.

Hvis sekvensen der elementene i treet skal nås, er ukjent på forhånd, kan splay -trær brukes som er asymptotisk like gode som alle statiske søketre vi kan konstruere for en bestemt sekvens av oppslagsoperasjoner.

Alfabetiske trær er Huffman -trær med ytterligere begrensning på bestilling, eller, tilsvarende, søker trær med endringen av at alle elementer er lagret i bladene. Raskere algoritmer finnes for optimale alfabetiske binære trær (OABT).

Se også

Merknader

Referanser

Videre lesning

Denne artikkelen inneholder materiale fra offentlig eiendom fra NIST -dokumentet: Black, Paul E. "Binary Search Tree" . Ordbok for algoritmer og datastrukturer .
Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "12: Binære søketrær, 15.5: Optimale binære søketrær". Introduksjon til algoritmer (2. utg.). MIT Press & McGraw-Hill. s. 253–272, 356–363. ISBN 0-262-03293-7.
Jarc, Duane J. (3. desember 2005). "Binary Tree Traversals" . Interaktive datastrukturvisualiseringer . University of Maryland . Arkivert fra originalen 27. februar 2014 . Hentet 30. april 2006 .
Knuth, Donald (1997). "6.2.2: Binary Tree Searching". The Computer of Computer Programming . 3: "Sortering og søk" (3. utg.). Addison-Wesley. s. 426–458. ISBN 0-201-89685-0.
Lang, Sean. "Binary Search Tree" ( PPT ) . Datastrukturer og algoritmer Visualisering-En PowerPoint-lysbildebasert tilnærming . SUNY Oneonta .
Parlante, Nick (2001). "Binære trær" . CS Education Library . Stanford University .

Eksterne linker

Ben Pfaff: En introduksjon til binære søketrær og balanserte trær . (PDF; 1675 kB) 2004.
Binary Tree Visualizer (JavaScript-animasjon av forskjellige BT-baserte datastrukturer)

Languages

In other projects