Drzewo bst doświadczenia

Question

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

Comments

#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

Answer 1

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).

Comments

usunięty