was ist der unterschied zwischen Heap und binary search Tree?

4 Antworten

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Java, Informatik, Programmieren & Softwareentwicklung

26.02.2024, 17:05

Bei einem Binary Search Tree sind die Elemente/Schlüssel (von links nach rechts) sortiert und typischerweise gibt es keine doppelten Elemente. Jeder Knoten enthält maximal zwei Kindknoten.

Bei einem Heap Tree gibt es allenfalls eine Ordnung von oben nach unten. Entweder muss der Schlüssel des Elternknoten stets kleiner im Wert sein, als seine Kindknoten (Min-Heap) oder größer (Max-Heap). Duplikate sind in so einer Baumstruktur erlaubt.

YaHobby

Fragesteller

26.02.2024, 17:07

was ist der Unterschied zwischen element und schlüssel

regex9

26.02.2024, 17:14

@YaHobby

Genau genommen ist ein Element das, was ein Knoten im Baum speichert. Jedes Element lässt sich durch einen Schlüssel identifizieren.

KarlRanseierIII

26.02.2024, 17:10

Danke für den Aspekt der Eindeutigkeit, den habe ich übersehen.

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

Informatik, Programmieren & Softwareentwicklung

26.02.2024, 17:04

Dazu müßtest Du Dir die Details zu beiden DS anschauen.

Beim binären Suchbaum herrscht eine totale Ordnung. Egal welchen Unterbaum Du Dir anschaust, die Ordnung ist immer so, daß auf einem Zweig alles kleiner, auf dem anderen alles größer ist.

Der binäre Heap ortientiert sich an den Anforderungen einer Prioritätswarteschlange, die Ordnung ist (als Baum visualisiert) vertikal gefolgt von horizontal.

Der Suchbaum soll eben insert, find, remove effektiv umsetzen, der heap insert, remove, ExtractMin, DecreaseKey.

Marcii21

27.02.2024, 07:47

Hey,

ich weiß leider nicht wie viel Erfahrung mit Sortieralgorithmen du bisher hattest, deshalb werde ich es eher allgemeiner erklären:

Ein Heap ist eine Baumstruktur, bei der die Elemente so angeordnet sind, dass das größte oder kleinste Element immer an der Wurzel (ganz oben) steht. Dadurch kann man das größte oder kleinste Element schnell finden und entfernen. Heaps werden oft für Prioritätswarteschlangen verwendet.

Ein Binary Search Tree (Binärer Suchbaum) ist eine Baumstruktur, bei der jedes Element so angeordnet ist, dass alle Elemente im linken Teilbaum kleiner und im rechten Teilbaum größer als das Wurzelelement sind. Dadurch kann man Elemente effizient suchen, einfügen und löschen.

Der Unterschied liegt also lediglich an der Organisation der Elemente.

Liebe Grüße,
Marcel

Woher ich das weiß:Studium / Ausbildung – Professionell & privat in Softwareentw., Selbststudium.

NorbertWillhelm

26.02.2024, 16:56

Heap ist ein Datenspeicherort, wohingegen ein binary search tree eine Datenstruktur ist.

Woher ich das weiß:Hobby

YaHobby

Fragesteller

26.02.2024, 16:58

aber heap ist ja auch ein baum

CSANecromancer

26.02.2024, 18:16

@YaHobby

Nein. Heap alleine und für sich ist nur ein Datenspeicherort.

YaHobby

Fragesteller

26.02.2024, 18:19

@CSANecromancer

man ey sach ma arbeitest du bei der nsa und hast den cosenamen Citizen Z

CSANecromancer

26.02.2024, 18:50

@YaHobby

Nein, ich arbeite als Softwareentwickler. Von daher muss ich extrem genau sein, denn z.B. der Computer und darauf laufende Compiler haben 0,0 Verständnis für Ungenauigkeiten.

YaHobby

Fragesteller

26.02.2024, 19:25

@CSANecromancer

schau dir mal Z nation an, du bist dabei Citizen Z

CSANecromancer

26.02.2024, 19:37

@YaHobby

Du redest wirr.

YaHobby

Fragesteller

26.02.2024, 19:44

@CSANecromancer

nene musst du mal machen, auf netflix nur die ersten 2 Folgen, da ist so ein Computer Profi, Citizen Z von der NSA im Camp Northern Light, der bist einfach du oder du bist er ? gönn dir mal wird dir safe gefallen

CSANecromancer

26.02.2024, 19:46

@YaHobby

Ach SO meinst du. Ok, danke für den Tip, schau ich mal rein.

YaHobby

Fragesteller

26.02.2024, 19:49

@CSANecromancer

jo, geb Bescheid obs dir gefallen hat.

CSANecromancer

28.02.2024, 01:16

@YaHobby

So, hab mal reingeschaut. Ist nicht so ganz mein Geschmack, aber ist ok. Nur mit Citizen Z hast du ziemlich unrecht. Jup, ich kann pedantisch sein und bemühe mich um Korrektheit bei technischen Begriffen, aber da hören die Parallelen auch schon auf. :)

Ähnliche Fragen

Binary Search Tree is Less?

Hallo, wie verwendet man den Operator is less in einem binary search tree? Ein Quelltext für Java/BlueJ würde mir sehr helfen

...zur Frage

Bin ich dumm, wenn ich Heap Exploits nicht verstehe?

Also z.B. wie man use after free ausnutzen kann.

https://ctf101.org/binary-exploitation/heap-exploitation/

...zur Frage

Kann mir jemand erklären wie genau dieser Java Integer to binary Converter funktioniert?

String binary=" ";

while(num > 0) {

binary = (num%2)+binary;

num /= 2;

}

...zur Frage

Wo ist der Unterschied zwischen einer normalen Datei und einem Blob?

Blob = Binary Large Object

Aber wenn auf einem Rechner nur mit Binären Werten gearbeitet wird, wo ist der Unterschied zum Blob?

...zur Frage

Informatik "Rätsel"?

Programmiersprache: JavaWie stellt man bei der Datenstruktur Queue Objekte nicht hinten sondern vorne an? Also vom Code her.Kontext/Hintergrund von dieser Frage: Ich habe eine PriorityQueue. Doch dann soll plötzlich ein neues Objekt hinzugefügt werden, welches eine höhere Priorität als alle bereits in der PriorityQueue vorhandenen Objekte hat. (Da das hinzuzufügende Objekt ja die höchste Priorität hätte, müsste es ganz vorne in der PriorityQueue stehen).
Natürlich habe ich mir, bevor ich die Frage hier auf GF stelle, selbst nachgedacht, wie man das Problem lösen könnte. Bis jetzt ist mir aber nur

first = new QueueInhalt(pObject, pPriority);

eingefallen. Ich komme beim setNext(), also wenn der neue, eingefügte, Knoten QueueInhalt seinen Next - Link auf den ursprünglich an derselben Stelle (ganz vorne) gewesenen Knoten QueueInhalt setzt. (Wenn man ein Objekt hinten anstellt, schön nach FIFO halt, hätte ich kein Problem mit dem Setzen der next - links und first - links. Aber vorne anstellen? Keine Ahnung, wie das gehen soll.)
Danke und ein "Hilfreich" schonmal für eure Antworten😀

public void add(ContentTypePerson pObject, int pPriority) {
    QueueInhalt inhaltsobjekt = new QueueInhalt(pObject, pPriority);
    if (first == null) { //Wenn kein Objekt in der Queue vorhanden ist
    first = new QueueInhalt(pObject, pPriority);
    } else if (pPriority > first.getPriority()) {
    first = new QueueInhalt(pObject, pPriority);
//...?    
    }
}

...zur Frage

C++: invalid use of non-static data member ...?

Hallo, ich habe in C++ einen Header für ein Projekt geschrieben aber ich kann innerhalb einer Klasse nicht auf eine Variable zugreifen.

Es kommt immer der Fehler:

..\ast.cpp:61:19: error: invalid use of non-static data member 'Tree::nodes'

p.set_type(Tree::nodes[id].get_type());

Hier ist der Code:

ast.h:

#ifndef AST_H_
#define AST_H_

class Tree {
public:
    class Node {
    public:
        enum class Type {
            METHOD,
            IF,
            WHILE,
            STATEMENT,
            EXPRESSION
        };

        void set_id(int id);
        void set_id_parent(int id_parent);
        void set_content(const char* content);
        void set_type(Type type);

        Type get_type();
        const char* get_content();
        int get_id();
        int get_parent_id();
        int* get_child_ids();

    private:
        Type m_type{};
        const char* m_content{};
        int  m_id=0;
        int  m_id_parent=-1;
        int* m_child_ids{};
    };

    void create_node(int parent, const char* content);

    Node get_node(int id);

private:
    Node* nodes{};
    int node_amount=0;
};

#endif

ast.cpp:

#include "ast.h"

void Tree::Node::set_id(int id) {
    m_id = id;
}

void Tree::Node::set_id_parent(int id_parent) {
    m_id_parent = id_parent;
}

void Tree::Node::set_content(const char *content) {
    m_content = content;
}

void Tree::Node::set_type(Type type) {
    m_type = type;
}

const char* Tree::Node::get_content() {
    return m_content;
}

Tree::Node::Type Tree::Node::get_type() {
    return m_type;
}

int Tree::Node::get_id() {
    return m_id;
}

int Tree::Node::get_parent_id() {
    return m_id_parent;
}

int* Tree::Node::get_child_ids() {
    return m_child_ids;
}

//

void Tree::create_node(int parent, const char *content) {
    Node p;
    p.set_id(node_amount);
    p.set_id_parent(parent);
    p.set_content(content);
    nodes[node_amount] = p;
    node_amount++;
}

Tree::Node get_node(int id) {
    Tree::Node p;
    p.set_type(Tree::nodes[id].get_type());
    return p;
}

Ich hoffe jemand kann mir sagen warum dieser Fehler kommt

Außerdem wollte ich etwas C benutzen und lernen, also hätte ich noch eine zweite Frage: Kann mir jemand sagen wie ich das ganze nicht in C++ sondern in C mache?

...zur Frage

LinkedList in Java sortieren beim Einfügen eines neuen Elements?

Ich habe hier den Code geschrieben, um ein neues Element einzufügen und danach die Liste zu sortieren.

Ich weiss, dass beides (Algorithmus für einfügen & Algorithmus fürs Sortieren) einzeln eigentlich funktionieren sollte. Aber die Kombination davon in einer Methode scheitert. Sieht jemand den Fehler.

Herzlichen Dank im Voraus!

...zur Frage

Was ist der Unterschied zwischen A-gender und Non-binary?

...zur Frage

Search Bar mir HTML, CSS; Java?

Wie kann ich eine Search Bar mit HTML, CSS und Java Code machen? Ich möchte, dass wenn man was eingibt, eine neue Seite geöffnet wird und auf dieser dann die Suchergebnisse angezeigt werden.

...zur Frage

Unterschied zwischen Java 8 und 17?

Hallo,

Java 8 ist schon älter, wo liegt aber der Unterschied dazwischen? Ist J17 eine Programmierumgebung oder was ist da anders, als beim aktuellen Java 8?

...zur Frage

Unterschied Scanner und BufferedReader?

"BufferedReader verwendet Zeichenströme, um Text aus der Eingabe zu lesen, während Scanner verwendet werden kann, wenn wir die primitive Art der Eingabe haben."

https://www.delftstack.com/de/howto/java/user-input-java/

Habe ich so im Internet gefunden, allerdings verstehe ich den Unterschied immer noch nicht. Zum Beispiel verstehe ich nicht, welchen Datentyp die Eingabe hat.

Was ich auch nicht verstehe: Scanner kann doch auch bei nicht-primitiven Arten verwendet werden, z.B. bei Strings mithilfe der nextLine()-Methode.

LG Kath

...zur Frage

pangender/non-binary?

Gibt es einen Unterschied zwischen pangender und non-binary?

wenn ja welchen?

...zur Frage

Unterschied zwischen robuster und defensiver Programmierung?

Ich verstehe nicht, was da der Unterschied ist. Beides bedeutet doch einfach nur, Exceptions anzukündigen und aufzufangen oder nicht?

...zur Frage

Rust error: `default-run` manifest key?

error: `cargo run` could not determine which binary to run. Use the `--bin` option to specify a binary, or the `default-run` manifest key.