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

Drzewo bst doświadczenia

Fiszki IT
Fiszki IT
0 głosów
154 wizyt
pytanie zadane 28 listopada 2020 w Matematyka, fizyka, logika przez dark41 Początkujący (460 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 Początkujący (460 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 (297,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 Początkujący (460 p.)
edycja 29 listopada 2020 przez dark41
usunięty

Podobne pytania

0 głosów
0 odpowiedzi 55 wizyt
pytanie zadane 20 czerwca 2020 w C i C++ przez Rrafał98 Nowicjusz (240 p.)
0 głosów
2 odpowiedzi 192 wizyt
pytanie zadane 14 grudnia 2018 w C i C++ przez Krystek102 Bywalec (2,430 p.)
0 głosów
1 odpowiedź 126 wizyt
pytanie zadane 24 maja 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)
Porady nie od parady
Możesz ukryć, zamknąć lub zmodyfikować swoje pytanie, za pomocą przycisków znajdujących się pod nim. Nie krępuj się poprawić pochopnie opublikowanego pytania czy zamknąć go po uzyskaniu satysfakcjonującej odpowiedzi. Umożliwi to zachowanie porządku na forum.Przyciski pytania

84,746 zapytań

133,553 odpowiedzi

295,967 komentarzy

56,007 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.

...