4

How do i implement a Queue using a BST.

Is this the way to do it, keep on inserting the nodes in the tree while maintaining a count value associated with each and every node,but while deletion BST should work like queue(FIFO) so start deleting from BST with the node having lowest count value in the tree.

Did i get the question and solution right? If not,then please explain me the question.

Sumit Kumar Saha
  • 799
  • 1
  • 12
  • 25

3 Answers3

3

A BST is really an inappropriate data structure to use to back a queue. You really ought to use a linked list instead, because it would be way faster, less complicated, and plain old better.

However, if you insist on using a BST...

You would use the BST as a priority queue, and define a wrapper type that also holds a 'queue index', which is what the items would be sorted by. You would have to define the comparison to take into account the current queue index though, because otherwise you could only ever add as many items as the difference between the highest and lowest values of your index type.

AJMansfield
  • 4,039
  • 3
  • 29
  • 50
  • Priority queue is implemeted using a max/min heap,then how a heap could be used as a BST or vice versa – Sumit Kumar Saha Nov 18 '12 at 22:46
  • @SumitKumarSaha Really, I didn't know. I thought c++ prority queue was implemented the same way as java's PriorityQueue, using a red-black tree. Apparently I was mistaken. Thank you for clarifying. – AJMansfield Nov 19 '12 at 12:10
  • Actually, it was Java's `SortedSet` or some such that uses Red-Black trees. `PriorityQueue` uses a heap. – AJMansfield Sep 18 '13 at 00:56
  • @OfirAttia No, you really can't. Use a heap for a priority queue, and either a ring buffer or linked nodes for any other type of queue. – AJMansfield Jan 25 '14 at 20:21
  • And if it just BST its ok? – Ofir Attia Jan 25 '14 at 20:25
  • 1
    @OfirAttia No. Queues have only a few operations: add an item (`add`), remove first item (`pop`), and examine the first item (`top`). A BST will have abominable performance compared to a heap, node list, or ring buffer for those operations, and is absolutely not acceptable. BSTs are used if one needs fast membership testing (`find`) or fast insertion (`insert`), which queues do not need. – AJMansfield Jan 25 '14 at 20:50
2

You can have a Queue like this:

BST // to store data
pointer to head; // Points to the head of the Queue
pointer to tail  // Points to the tail of the Queue

You add to the nodes structs of BST also a pointer to another node that will represent the order of insertion.

struct Node{
  int x;
  //left pointer
  //right pointer
  struct Node *next_queune_element;
}

During the insertion When you want to add an element, you first access the node that the pointer tail points to and make it point to the new element that you just inserted (the BST node). Then you update the tail pointer to point to the new element.

During the deletion When you remove an element, you first access the node that the head pointer points to, you store the next_queune_element in an auxiliary temporary variable and remove the node. Finally, make the head pointer to point to the auxiliary temporary variable.

dreamcrash
  • 47,137
  • 25
  • 94
  • 117
  • Its efficent, and although its not actually a BST, it is really better than a BST for this application. – AJMansfield Nov 19 '12 at 12:11
  • For a BST you need to do "right rotations" and "left rotations" to keep the tree balanced otherwise it gets messy, so for insertion deletion TMK IRL it's a bit more complicated – Alexander Mills Dec 23 '22 at 01:32
  • is it better to implement using BST or with Min Heap or Max Heap? – Alexander Mills Dec 24 '22 at 03:39
  • @AlexanderMills Hi Thanks for the comment, however, it has been a longer time since I learn about the topic. In this thread you can find a better answer https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst – dreamcrash Dec 24 '22 at 22:26
0

I think a binary tree would be the desired data structure here and not a binary search tree. Using a binary tree for implementing a queue might be usefull when doing functional programming. You can do it using a binary tree which stays height balanced after each push and pop operation so they will always be O(log n). Push and pop look like:

  • a function to insert an element to the very left of the tree (the push function);
  • a function to delete an element from the very right of the tree (the pop fuction).

In both cases rebalancing won't violate the insertion order. Both are easy too implement as well. You are in fact using an AVL tree with altered insert functions. A bonus is the elements do not need to be (totally) orderable.

Elmex80s
  • 3,428
  • 1
  • 15
  • 23