• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Drzewo bst doświadczenia

0 głosów
189 wizyt
pytanie zadane 28 listopada 2020 w Matematyka, fizyka, logika przez dark41 Użytkownik (580 p.)

witam,

jak robi się doświadczenia na drzewach bst mam zadanie do wykonania:

zbadać doświadczalnie średnią wysokość drzew BST budowanych z losowych elementów.

Dodatkowo sprawdzić średni czas wykonania operacji wstawiania, poszukiwania i usuwania

elementów z drzewa. Doświadczenia przeprowadzić dla drzew o różnej ilości elementów (np.

od 10^4 do 10^6 z krokiem 10^4) i liczb losowanych ze zbiorów o mocy (ilości

elementów):10^9, 1000, 10, 2

Czy muszę rysować te drzewa czy podstawiać jakieś wartości do pseudokodu ?

to moje pierwsze spotkanie z bst oglądałem rożne tutoriale itp ale wiem tylko że wartości mniejsze są po lewej a większe po prawej

komentarz 29 listopada 2020 przez dark41 Użytkownik (580 p.)
edycja 29 listopada 2020 przez dark41
#include <iostream>
#include <stdlib.h>
#include <stdio.h> 
#include <string.h> 
#include <cstdlib>
using namespace std;

struct Node{
    int Data;
    Node *left;
    Node *right;
};

class BSTree{
private:
    Node *Root;

    void __Insert(Node *&root, int data){
        if (root == NULL){
            root = new Node();
            root->Data = data;
            root->left = NULL;
            root->right = NULL;
        }
        else{
            if (data < root->Data){
                __Insert(root->left, data);
            }
            else{
                __Insert(root->right, data);
            }
        }
    }

    void __Print(Node *root){
        if (root == NULL){
            return;
        } else{
            cout << root->Data << " ";    //Preorder
            __Print(root->left);
            //cout << root->Data << " "; //Inorder
            __Print(root->right);
            //cout << root->Data << " "; //Postorder
        }
    }

    int __Height(Node *root){
        if (root == NULL){
            return 0;
        } else{
            int ldepth = __Height(root->left);
            int rdepth = __Height(root->right);

            if (ldepth > rdepth){
                return 1 + ldepth;
            }else{
                return 1 + rdepth;
            }
        }
    }
public:
    BSTree(){
        Root = NULL;
    }

    void Insert(int x){
        if (Root == NULL){
            Root = new Node();
            Root->Data = x;
            Root->left = NULL;
            Root->right = NULL;
        } else{
            __Insert(Root, x);
        }
    }

    int Height(){
        return __Height(Root);
    }



    void PrintTree(){
        __Print(Root);
    }
};

int main(){
    BSTree MyTree;

    for (int i = 0; i < 100000; i++){
        int num = rand() % 100000;
        cout << num << " ";
        MyTree.Insert(num);
    }

    cout << endl << endl;

    MyTree.PrintTree();

    cout << endl << MyTree.Height() << " " << endl;
    return 0;
}

czy to będzie poprawne program dodaje do drzewa 100000 elementów ze zbioru 10000 i wylicza wysokość drzewa czy jeśli wykonam ten program kilkukrotnie i wyliczę średnią wysokość drzew będzie to poprawne? następnie z inna ilością elementów i innym zbiorem

1 odpowiedź

0 głosów
odpowiedź 28 listopada 2020 przez adrian17 Ekspert (306,380 p.)

zbadać doświadczalnie średnią wysokość drzew BST

Zbuduj drzewo z jakąś liczbą elementów, przeiteruj się po nim, policz programowo głębokość.

Dodatkowo sprawdzić średni czas wykonania operacji wstawiania, poszukiwania i usuwania

Wykonaj operację dużo (N) razy, zmierz czas wykonania, policz średni czas (dzieląc przez N).

komentarz 28 listopada 2020 przez dark41 Użytkownik (580 p.)
edycja 29 listopada 2020 przez dark41
usunięty

Podobne pytania

0 głosów
0 odpowiedzi 63 wizyt
pytanie zadane 20 czerwca 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)
0 głosów
0 odpowiedzi 25 wizyt
pytanie zadane 14 godziny temu w C i C++ przez Czang Kai Shrek Obywatel (1,410 p.)
0 głosów
2 odpowiedzi 220 wizyt
pytanie zadane 14 grudnia 2018 w C i C++ przez Krystek102 Bywalec (2,440 p.)

86,412 zapytań

135,170 odpowiedzi

300,266 komentarzy

57,170 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...