złożoność czasowa i pamięciowa algorytmu inOrder (chyba inaczej sortowanie Stogowe) w drzewie poszukiwań binarnych

Question

hej, ostatnio natknąłem się na bardzo ciekawy algorytm sortowania wykorzystujący drzewo binarne - *a nie kopiec* (nigdy o nim nie słyszałem w kursie Pana Mirosława ani na żadnych stronach) ,mowa tu o inOrder (przynajmniej ja tak to nazwałem :D) . Nie mogłem znaleźć na temat tego algorytmu więcej informacji ,nie wiem czemu bo dla mnie jest bardzo ciekawy (może nawet lepszy od Heap sort którego niezbyt lubię)  . By uniknąć problemów podam cały kod sortowania oraz moją implementacje całego drzewa binarnego - co o niej sądzicie co mogę poprawić ? . Z góry dziękuje za odpowiedzi i komentarze oraz pozdrawiam :)

oto kod samego inOrder:

void inOrder(DataTrees *parent) { //sosrtowaanioe
	if (parent) {
		inOrder(parent->leftChild);
		cout << parent->data << " ";
		inOrder(parent->rightChild);
	}
}

Cały program (napisany w VS więc w pliku stdafx mamy biblioteki):

#include "stdafx.h"

using namespace std;

struct DataTrees {
	int data;
	DataTrees *leftChild;
	DataTrees *rightChild;
};

void add(DataTrees *&parent, int value) { //wstawaianie elementu 
	if (!parent) { //jezeli jest tu puste mijsce
		parent = new DataTrees;
		parent->data = value;
		parent->leftChild = nullptr;
		parent->rightChild = nullptr;
	}
	else { //pezeszukiwanie 
		if (value >= parent->data) add(parent->rightChild, value);
		else add(parent->leftChild, value);
	}
}

void inOrder(DataTrees *parent) { //sosrtowaanioe
	if (parent) {
		inOrder(parent->leftChild);
		cout << parent->data << " ";
		inOrder(parent->rightChild);
	}
}

void find(DataTrees *parent, DataTrees *&element, int value) { //poszukiwanie danej wartosci i ustawianie wskaznika na odpowiedni obiekt 
	if (!parent) { //jezeli nie znaleziono i nie ma juzz wiecej elementow 
		cout << "error" << endl;
	}
	else if (parent->data == value) { //jezeli znaleziono
		element = parent;
		cout << "is good! " << endl;
	}
	else { //poszukiwanie binarne 
		if (value < parent->data) find(parent->leftChild,element,value);
		else find(parent->rightChild, element, value);
	}
}

void deleteTree(DataTrees *&element) { //usowanie drzewa 
		if(element)deleteTree(element->leftChild);
		if(element)deleteTree(element->rightChild);
		element = nullptr;
}


int main()
{
	DataTrees *root = nullptr;
	DataTrees *element = nullptr;

	while (true) {
		cout << "---MENU---" << endl;
		cout << "1. add" << endl;
		cout << "2. inOrder" << endl;
		cout << "3. find" << endl;
		cout << "4. show find element" << endl;
		cout << "5. delete tree" << endl;
		cout << "----------" << endl;

		char z = _getch();

		switch (z) {
		case '1': {
			cout << "value: ";
			int v; cin >> v;
			add(root, v);
			break;
		}
		case '2': {
			if (root) {
				cout << "sort: ";
				if(root) inOrder(root);
				else cout << 0;
			}
			else cout << 0 << endl;

			_getch();
			break;
		}
		case '3': {
			cout << "value: ";
			int v; cin >> v;
			find(root, element, v);
			_getch();
			break;
		}
		case '4': {
			if (element) {
				cout << "value: " << element->data << endl;
			}
			else cout << 0 << endl;
			_getch();
			break;
		}
		case '5': {
			deleteTree(root);
			break;
		}
		}

		system("cls");
	}

    return 0;
}

 

Comments

Aaa, już odkryłem że ten algorytm inaczej nazywa się sortowaniem stogowym ,ale i tak nie znalazłem zbytnio informacji na temat jego złożoności (po za tym wyskakuje mi wtedy w większości przypadków sortowanie przez kopcowanie a nie to)

---

Aaa, już odkryłem że ten algorytm inaczej nazywa się sortowaniem stogowym

O tym już wiedziałeś zakładając temat przecież ;)

---

nie wiedziałem ,zmieniłem nazwę tematu już po czasie

Answer 1

Nie możesz znaleźć informacji o tym sortowaniu ponieważ to nie jest sortowanie. Drzewo binarne z definicji zachowuje porządek na węzłach więc to co robi twoja funkcja inOrder to poprostu wypisuje to w dobrej kolejności.
Algorytmem sortującym można by byo nazwać procedurę która:

1. Tworzy puste drzewo.
2. Dodaje kolejne elementy do drzewa
3. Wypisuje je inOrder.

Wtedy taka procedura ma złożoność zgrubsza O(n log n) gdzie n to liczba elementów co jest porównywalne z quicksortem/ mergesortem i innymi algorytmami o takiej złożoności.

Dlaczego taka złożoność?
Krok drugi działa w czasie O(log n) dla każdego z n elementów co daje nam sumaryczną złożonośc taką jak napisałem.
Krok 3 działa w czasie O(n). NIe należy myśleć że zatem sortuje on w czasie liniowym (bo krok 3 jest liniowo) bo jest tak tylko dlatego że sturuktura ma taką własność że jest w pewien szczególny sposób uporządkowana

Comments

dzięki ,właśnie to miałem na myśli .Podałem cały kod bo właśnie sądziłem że sortowanie stanowi to jako całość .Jestem dość zadowolony z tego wykorzystania drzewa bo jak sam napisałeś złożoność wynosi O(n log n) więc jest dość szybka i po za tym zrobiłem jeszcze testy porównawcze z innymi algorytmami . Dzięki jeszcze raz i pozdrawiam

---

Tak te trzy punkty które Gumiś wymienił to sortowanie drzewiaste
i różni się nieco od stogowego 
Ja go używam do sortowania list
(dla listy jednokierunkowej wskaźnik na poprzednika jest używany przez drzewo BST)
Procedura wstawiającą węzły listy do drzewa i
procedurę przekształcającą drzewo w listę przechodząc drzewo w kolejności inOrder
mam napisane rekurencyjnie
Asymptotyczna złożoność czasowa taka sama jak dla sortowania przez podział
O(nlog(n)) w średnim przypadku , O(n^2) w przypadku pesymistycznym
Przypadek pesymistyczny występuje gdy nasze drzewko redukuje się do listy

 

---

Dzięki za chęć pomocy. Ale to pytanie jest zamknięte od roku... :/

---

Tak ale może się przydać też innym
Dziwne  te praktyki zamykania tematów

choć są charakterystyczne dla pewnej grupy osób, szczególnie młodych

Answer 2

To jest drzewo BST, jego lepsze wersje to drzewo czerwone czarne i AVL

Comments

Dzięki za ważną informację  ,chociaż na start ten rodzaj drzewa powinien mi wystarczyć (no bo co mi na razie przeszkadza że lewe pod drzewo jest większe od prawego) . Wiesz może jeszcze jaka jest albo gdzie można znaleźć informacje na temat złożoności algorytmu sortowania użytego w tym programie ?

---

*bo nie wiem czy się opłaca go stosować

Answer 3

Nigdzie nie można znaleźć informacji? https://pl.wikipedia.org/wiki/Sortowanie_przez_kopcowanie

Comments

Autor pisał, że nie o to chodzi

---

dzięki za chęć pomocy ale w pytaniu pisze tak:

hej, ostatnio natknąłem się na bardzo ciekawy algorytm sortowania wykorzystujący drzewo binarne - *a nie kopiec*

logiczne że sortowanie przez kopcowanie jest tak znane że sam na nie wpadam :) 

---

No nie wiem, tak jest napisane w komentarzu do pytania

---

no czyli dobrze napisałeś że nie sortowanie dzięki kopcowi miałem na myśli