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

Drzewo bst doświadczenia

VPS Starter Arubacloud
0 głosów
444 wizyt
pytanie zadane 28 listopada 2020 w Matematyka, fizyka, logika przez dark41 Użytkownik (760 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 (760 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 (344,100 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 (760 p.)
edycja 29 listopada 2020 przez dark41
usunięty

Podobne pytania

0 głosów
0 odpowiedzi 128 wizyt
pytanie zadane 20 czerwca 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)
0 głosów
0 odpowiedzi 212 wizyt
pytanie zadane 18 stycznia 2022 w C i C++ przez Czang Kai Shrek Obywatel (1,990 p.)
0 głosów
2 odpowiedzi 316 wizyt
pytanie zadane 14 grudnia 2018 w C i C++ przez Krystek102 Bywalec (2,440 p.)

92,451 zapytań

141,261 odpowiedzi

319,073 komentarzy

61,853 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...