algorithm - 如果一个节点等于二叉搜索树中的父节点，我们将它放在哪一边

Question

我正在学习数据结构和算法。特别是，我正在学习二叉搜索树 (BST)。

我的问题，正如标题所暗示的，如果我们放置一个值，并且它等于它的父级，我们应该把它放在哪一边？左侧是小于父级的值，右侧是大于父级的值。那么，我们在哪里放置一个等于父级的值呢？

感谢您对此的任何帮助。

Answer 1

没有一个普遍认可的标准方法来做到这一点。有些人根本不允许 BST 存储重复项，基本上定义了这个问题。 (这就是您在将树用于 map 和集合时经常看到的)。其他实现可能将所有相同的键存储在同一个节点中，可能通过使用链表。其他人可能会说左子树包含较小的键，而右子树包含大于或等于节点自身键的键。

每种方法都有优点和缺点，您可以选择最适合您的用例的方法。