Unterschied zwischen Binärbaum und Binärsuchbaum

Antworten:

566

Binärbaum: Baum, in dem jeder Knoten bis zu zwei Blätter hat

  1
 / \
2   3

Binärer Suchbaum: Wird für die Suche verwendet . Ein Binärbaum, in dem das linke untergeordnete Element nur Knoten mit Werten enthält , die kleiner als der übergeordnete Knoten sind, und in dem das rechte untergeordnete Element nur Knoten enthält, deren Werte größer oder gleich dem übergeordneten Knoten sind.

  2
 / \
1   3
user541686
quelle
14
@pete: Es ist eine konzeptionelle Sache, Sie werden nicht unbedingt jemals eine machen, die völlig uneingeschränkt ist. Es gibt jedoch viele nicht suchende Binärbäume, die auf andere Weise speziell sind, z. B. Binärhaufen.
user541686
19
@pete Birary-Bäume müssen nicht unbedingt vergleichbare Daten enthalten. Viele (nicht suchende) Binärbäume werden zum Parsen des algebraischen Ausdrucks verwendet. Der Binärbaum ist perfekt, um einen Parser für die Infixnotation zu schreiben, indem der Operator als Knoten und numerische Werte platziert wird als Blätter
JBoy
2
@JBoy: In diesem Fall werden sie jedoch keine Binärbäume sein. (zB unäre Operatoren können keine zwei Kinder haben.) Ich kann mir wirklich keinen praktischen Anwendungsfall für nicht eingeschränkte Binärbäume vorstellen, deshalb habe ich diesen Kommentar abgegeben.
user541686
2
Großartig und einfach. +1 für visuelles Beispiel :)
Andrei Konstantinov
@Mehrdad Ein Binärbaum hat ein oder zwei untergeordnete Elemente pro Knoten. Ausdrucksbäume sind ein perfektes Beispiel. Ein binärer Suchbaum auch ein oder zwei Kinder pro Knoten, es wäre denn , es voll sein geschieht, das nur mit bestimmten Anzahl von Elementen passieren kann.
Marquis von Lorne
56

Der binäre Baum ist eine spezielle Baumform mit zwei Kindern (linkes Kind und rechtes Kind). Es ist einfach eine Darstellung von Daten in der Baumstruktur

Der binäre Suchbaum (BST) ist ein spezieller Typ eines binären Baums, der folgende Bedingung erfüllt:

  1. Der linke untergeordnete Knoten ist kleiner als der übergeordnete Knoten
  2. Der rechte untergeordnete Knoten ist größer als der übergeordnete Knoten
Jayzcode
quelle
23
Diese Bedingungen reichen nicht aus. Der gesamte linke Teilbaum darf keine Schlüssel enthalten, die nur kleiner als die des übergeordneten sind, und der gesamte rechte Teilbaum darf Knoten größer enthalten.
Marquis von Lorne
1
@EJP kannst du bitte deinen Kommentar ausarbeiten? Was meinst du mit dem gesamten Teilbaum? Sie meinen, alle Werte des Teilbaums sollten kleiner sein als auf der linken Seite zu wurzeln? und alle Werte sollten größer sein als der Wurzelwert auf der rechten Seite?
Asif Mushtaq
Lesen Sie nach dem zweiten Link den Abschnitt "Überprüfung" und es wird klar.
Rob
38

Ein Binärbaum besteht aus Knoten, wobei jeder Knoten einen "linken" Zeiger, einen "rechten" Zeiger und ein Datenelement enthält. Der "Wurzel" -Zeiger zeigt auf den obersten Knoten im Baum. Der linke und der rechte Zeiger zeigen rekursiv auf kleinere "Teilbäume" auf beiden Seiten. Ein Nullzeiger repräsentiert einen Binärbaum ohne Elemente - den leeren Baum. Die formale rekursive Definition lautet: Ein Binärbaum ist entweder leer (dargestellt durch einen Nullzeiger) oder besteht aus einem einzelnen Knoten, wobei der linke und der rechte Zeiger (rekursive Definition voraus) jeweils auf einen Binärbaum zeigen.

Ein binärer Suchbaum (BST) oder "geordneter binärer Baum" ist eine Art binärer Baum, bei dem die Knoten in der richtigen Reihenfolge angeordnet sind: Für jeden Knoten sind alle Elemente in seinem linken Teilbaum kleiner als der Knoten (<) und alle Elemente in seinem rechten Teilbaum sind größer als der Knoten (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

Der oben gezeigte Baum ist ein binärer Suchbaum - der "Wurzel" -Knoten ist eine 5, und seine linken Teilbaumknoten (1, 3, 4) sind <5 und seine rechten Teilbaumknoten (6, 9) sind> 5. Rekursiv muss jeder der Teilbäume auch die Einschränkung des binären Suchbaums erfüllen: Im Teilbaum (1, 3, 4) ist die 3 die Wurzel, die 1 <3 und 4> 3.

Achten Sie auf den genauen Wortlaut der Probleme - ein "binärer Suchbaum" unterscheidet sich von einem "binären Baum".

Emmanuel Oddy
quelle
@GabrielStaples Baumstruktur hinzugefügt.
Gaurav Borole
14

Wie jeder oben über den Unterschied zwischen Binärbaum und Binärsuchbaum erklärt hat, füge ich nur hinzu, wie man testet, ob der angegebene Binärbaum ein Binärsuchbaum ist.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

Hoffe es wird dir helfen. Es tut mir leid, wenn ich vom Thema ablenke, da ich der Meinung bin, dass es sich lohnt, dies hier zu erwähnen.

Ich versuche es
quelle
1
Entweder der linke oder der rechte Teilbaum kann leer sein. Ihr Code behandelt diesen Fall nicht richtig.
Marquis von Lorne
11

Binary Tree steht für eine Datenstruktur , die aus besteht Knoten , die kann nur haben zwei Kinder Referenzen.

Binary Search Tree ( BST ) hingegen ist eine spezielle Form der Binary Tree- Datenstruktur, bei der jeder Knoten einen vergleichbaren Wert hat und Kinder mit kleinerem Wert links und Kinder mit größerem Wert rechts zugeordnet sind.

Somit sind alle BST 's sind Binary Tree jedoch nur einige Binary Tree ' s kann auch sein , BST . Benachrichtigen Sie, dass BST eine Teilmenge des Binärbaums ist .

Der binäre Baum ist also eher eine allgemeine Datenstruktur als der binäre Suchbaum . Außerdem müssen Sie benachrichtigen, dass der binäre Suchbaum ein sortierter Baum ist, während es für den generischen binären Baum keine solchen Regeln gibt .

Binärer Baum

A Binary Treewas nicht a ist BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Binärer Suchbaum (sortierter Baum)

Ein binärer Suchbaum, der auch ein binärer Baum ist ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Eigenschaft des binären Suchbaumknotens

Benachrichtigen Sie dies auch für jeden übergeordneten Knoten in der BST .

  • Alle linken Knoten haben einen kleineren Wert als der Wert des übergeordneten Knotens. Im oberen Beispiel sind die Knoten mit den Werten {20, 25, 30}, die sich alle links ( linke Nachkommen ) von 50 befinden, kleiner als 50.

  • Alle rechten Knoten haben einen größeren Wert als der Wert des übergeordneten Knotens. Im oberen Beispiel sind die Knoten mit den Werten {70, 75, 80}, die sich alle rechts ( rechte Nachkommen ) von 50 befinden, größer als 50.

Es gibt keine solche Regel für den Binärbaumknoten . Die einzige Regel für den Binärbaumknoten besteht darin, zwei Kinder zu haben, sodass er sich selbst erklärt, warum er als Binär bezeichnet wird .

Levent Divilioglu
quelle
Können wir Simple Binary Tree implementieren? Gibt es eine Implementierung? und was nützt dieser Baum?
Asif Mushtaq
@UnKnown Sie können den binären Suchbaum zum Sortieren und Suchen verwenden. Die Implementierung des binären
Suchbaums
Ich weiß davon, aber gibt es eine Existenz von Simple Tree oder Simple Binary Tree? oder irgendeine Implementierung von Simple Binary Tree?
Asif Mushtaq
Es macht keinen Sinn, dies zu verwenden, aber Sie können dem Stamm und den untergeordneten Knoten beliebige Knoteninstanzen hinzufügen.
Levent Divilioglu
10

Ein binärer Suchbaum ist eine spezielle Art von Binärbaum, der die folgende Eigenschaft aufweist: Für jeden Knoten n ist der Wert jedes Nachkommenknotens im linken Teilbaum von n kleiner als der Wert von n, und der Wert jedes Nachkommenknotens im rechten Teilbaum ist größer als der Wert von n.

Kaushik Lele
quelle
8

Binärer Baum

Binärbaum kann alles sein, was 2 Kinder und 1 Elternteil hat. Es kann als verknüpfte Liste oder Array oder mit Ihrer benutzerdefinierten API implementiert werden. Sobald Sie anfangen, spezifischere Regeln hinzuzufügen, wird der Baum spezialisierter . Die bekannteste Implementierung ist, dass links kleinere und rechts größere Knoten hinzugefügt werden.

Zum Beispiel ein beschrifteter Binärbaum der Größe 9 und Höhe 3 mit einem Wurzelknoten, dessen Wert 2 ist. Der Baum ist unausgeglichen und nicht sortiert . https://en.wikipedia.org/wiki/Binary_tree

Geben Sie hier die Bildbeschreibung ein

Im Baum links hat A beispielsweise die 6 Kinder {B, C, D, E, F, G}. Es kann rechts in den Binärbaum konvertiert werden.

Geben Sie hier die Bildbeschreibung ein

Binäre Suche

Die binäre Suche ist eine Technik / ein Algorithmus, mit der ein bestimmtes Element in der Knotenkette gefunden wird. Die binäre Suche funktioniert bei sortierten Arrays .

Die binäre Suche vergleicht den Zielwert mit dem mittleren Element des Arrays. Wenn sie ungleich sind, wird die Hälfte, in der das Ziel nicht liegen kann, eliminiert und die Suche in der verbleibenden Hälfte fortgesetzt, bis sie erfolgreich ist oder die verbleibende Hälfte leer ist. https://en.wikipedia.org/wiki/Binary_search_algorithm

Geben Sie hier die Bildbeschreibung ein

Ein Baum, der die binäre Suche darstellt . Das hier gesuchte Array ist [20, 30, 40, 50, 90, 100] und der Zielwert ist 40.

Geben Sie hier die Bildbeschreibung ein

Binärer Suchbaum

Dies ist eine der Implementierungen des Binärbaums. Dies ist auf die Suche spezialisiert .

Binäre Suchbaum- und B-Baum-Datenstrukturen basieren auf binärer Suche .

Binäre Suchbäume (BST), manchmal auch geordnete oder sortierte Binärbäume genannt, sind eine bestimmte Art von Container : Datenstrukturen, in denen "Elemente" (wie Zahlen, Namen usw.) gespeichert sind. https://en.wikipedia.org/wiki/Binary_search_tree

Ein binärer Suchbaum der Größe 9 und Tiefe 3 mit 8 an der Wurzel. Die Blätter sind nicht gezeichnet.

Geben Sie hier die Bildbeschreibung ein

Und schließlich ein großartiges Schema für den Leistungsvergleich bekannter Datenstrukturen und angewandter Algorithmen:

Geben Sie hier die Bildbeschreibung ein

Bild aus Algorithmen (4. Auflage)

Teoman Shipahi
quelle
4

Ein binärer Baum ist ein Baum, dessen Kinder niemals mehr als zwei sind. Ein binärer Suchbaum folgt der Invariante, dass das linke Kind einen kleineren Wert als der Schlüssel des Wurzelknotens haben sollte, während das rechte Kind einen größeren Wert als der Schlüssel des Wurzelknotens haben sollte.

Nana Yaah
quelle
4
  • Binärer Suchbaum: Wenn die Inorder Traversal für den Binärbaum durchgeführt wird, erhalten Sie sortierte Werte der eingefügten Elemente
  • Binärbaum: In keiner Art von Durchquerung wird eine sortierte Reihenfolge gefunden
AlienOnEarth
quelle
Keine sortierter Reihenfolge muss gefunden werden. Ein binärer Suchbaum ist auch ein binärer Baum. Sie schließen sich nicht gegenseitig aus. BST ist eine richtige Teilmenge von BT.
Marquis von Lorne
3

Um zu überprüfen, ob ein bestimmter Binärbaum ein binärer Suchbaum ist, ist hier ein alternativer Ansatz.

Baum in unordentlicher Weise durchlaufen (dh linkes Kind -> Eltern -> rechtes Kind), durchquerte Knotendaten in einer temporären Variablen speichern , sagen wir temp , kurz vor dem Speichern in temp , prüfen, ob die Daten des aktuellen Knotens höher sind als die vorherigen oder nicht . Dann brechen Sie es einfach aus, Baum ist kein binärer Suchbaum, sonst durchlaufen Sie bis zum Ende.

Unten ist ein Beispiel mit Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Behalten Sie die Temperaturvariable außerhalb bei

Neeraj Jain
quelle
Jeder Teilbaum kann null sein. Ihr Algorithmus behandelt diesen Fall nicht richtig.
Marquis von Lorne
1

In einem binären Suchbaum sind alle Knoten in einer bestimmten Reihenfolge angeordnet - Knoten links von einem Wurzelknoten haben einen kleineren Wert als seine Wurzel, und alle Knoten rechts von einem Knoten haben Werte, die größer als der Wert von sind Wurzel.

Spencer Cheng
quelle
0

Ein Baum kann genau dann als Binärbaum aufgerufen werden, wenn die maximale Anzahl von untergeordneten Elementen eines der Knoten zwei beträgt.

Ein Baum kann genau dann als binärer Suchbaum aufgerufen werden, wenn die maximale Anzahl von untergeordneten Elementen eines der Knoten zwei beträgt und das linke untergeordnete Element immer kleiner als das rechte untergeordnete Element ist.

jith912
quelle