使用二叉搜索树实现队列

Question

我如何使用二叉搜索树实现队列？

这样做的方式是，保持将节点插入树中，并同时维护与每个节点相关联的计数值，但在删除二叉搜索树时应该像队列（FIFO）一样工作，因此从具有最低计数值的节点开始从二叉搜索树中删除。

如果我理解问题和解决方案错误，请解释问题。

- Sumit Kumar Saha

Answer 1

一个二叉搜索树(BST)并不适合用作队列的数据结构。相反，你应该使用链表代替BST，因为它更快、更简单，而且更好。

然而，如果你坚持要使用BST...

你可以将BST用作优先队列，并定义一个包装类型，该类型还包含一个'队列索引'，这就是项目排序的方式。你必须定义比较函数以考虑当前队列索引，否则你只能添加等于索引类型最高和最低值之差的项数。

- AJMansfield

---

优先队列是使用最大/最小堆实现的，那么如何将堆用作二叉搜索树或反之亦然？ - Sumit Kumar Saha

@SumitKumarSaha 真的吗？我不知道。我认为C++优先队列与Java的PriorityQueue以相同的方式实现，使用红黑树。显然我错了。谢谢你澄清。 - AJMansfield

实际上，这是Java的SortedSet或类似使用红黑树的数据结构。而PriorityQueue则使用堆。 - AJMansfield

@OfirAttia 不行，你真的不行。使用堆来实现优先队列，对于其他类型的队列，可以使用环形缓冲区或链式节点。 - AJMansfield

如果只是二叉搜索树，可以吗？ - Ofir Attia

@OfirAttia 不行。队列只有几个操作：添加一个项目（add），删除第一个项目（pop）和检查第一个项目（top）。与堆、节点列表或环形缓冲区相比，BST 在这些操作中的性能非常糟糕，绝对不可接受。如果需要快速成员测试（find）或快速插入（insert），则使用 BST，而队列不需要。 - AJMansfield

Answer 2

您可以创建一个类似这样的队列：

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

你需要在BST的节点结构中添加一个指向另一个节点的指针，该节点将代表插入顺序。

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

插入节点 当您想要添加一个元素时，首先访问指针尾部指向的节点并将其指向您刚刚插入的新元素（BST节点）。然后，更新尾指针以指向新元素。

删除节点 当您删除一个元素时，首先访问头指针指向的节点，将next_queune_element存储在辅助临时变量中并删除节点。最后，使头指针指向辅助临时变量。

- dreamcrash

---

它很高效，虽然它实际上并不是二叉搜索树，但对于这个应用程序来说确实比二叉搜索树更好。 - AJMansfield

对于二叉搜索树，为了保持平衡，您需要进行“右旋转”和“左旋转”，否则它会变得混乱。因此，在插入删除等操作方面，情况会更加复杂。 - Alexander Mills

使用二叉搜索树（BST）还是最小堆或最大堆实现更好？ - Alexander Mills

@AlexanderMills 您好，感谢您的评论。不过我已经有一段时间没学习这个主题了。在这个帖子里，您可以找到更好的答案：https://dev59.com/MG025IYBdhLWcg3wNTEV - dreamcrash

Answer 3

我认为这里需要使用二叉树而不是二叉搜索树作为所需的数据结构。在进行函数式编程时，使用二叉树实现队列可能会很有用。您可以使用一个二叉树，在每次推入和弹出操作后保持平衡，因此它们将始终是O(log n)。推入和弹出看起来像：

• 插入元素到树的最左边的函数（即推入函数）；
• 从树的最右边删除元素的函数（即弹出函数）。

在这两种情况下，重新平衡不会违反插入顺序。两者都很容易实现。实际上，您正在使用具有更改插入函数的AVL树。奖励是元素不需要（完全）可排序。

- Elmex80s