tas vs un arbre de recherche binaire

Question

Quelle est la différence entre un segment et de la BST?

Quand utiliser un tas et quand utiliser un BST?

Si vous voulez obtenir les éléments triés de la mode, est cest mieux au fil du tas?

Answer 1

Tas juste garantit que les éléments sur les niveaux les plus élevés sont plus (pour max-heap) ou plus petite (pour min-tas) que des éléments sur les niveaux inférieurs, tandis que la BST, les garanties de commande (de "gauche" et "droite"). Si vous voulez éléments triés, aller avec BST.

Answer 2

Quand utiliser un tas et quand utiliser un BST

Tas est mieux à findMin/findMax (O(1)), tandis que le BST est bon à tous les trouve (O(logN)). Insert O(logN) pour les deux structures. Si vous ne se soucient findMin/findMax (par exemple, la priorité), aller avec le tas. Si vous voulez tout trié, aller avec BST.

D'abord quelques diapositives à partir d' ici expliquer les choses très clairement.

Answer 3

Un arbre de recherche binaire utilise la définition: pour chaque nœud,le nœud de la gauche, a une moindre valeur(key) et le nœud à la droite de celui-ci a une plus grande valeur(key).

Où, comme le tas,en cours de mise en œuvre d'un arbre binaire utilise la définition suivante:

Si A et B sont des nœuds, où B est l'enfant du nœud A,puis la valeur(key) de l'Un doit être supérieure ou égale à la valeur(key) de B. C'est, clé(Un) ≥ touche(B).

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

J'ai couru dans la même question aujourd'hui pour mon examen et je l'ai eu droit. sourire ... :)

Answer 4

Insérez tous les n éléments d'un tableau à la STB prend O(n logn). n elemnts dans un tableau peut être inséré à un segment de mémoire en O(n) fois. Ce qui donne tas un avantage certain