我正在学习数据结构和算法。特别是,我正在学习二叉搜索树 (BST)。
我的问题,正如标题所暗示的,如果我们放置一个值,并且它等于它的父级,我们应该把它放在哪一边?左侧是小于父级的值,右侧是大于父级的值。那么,我们在哪里放置一个等于父级的值呢?
感谢您对此的任何帮助。
最佳答案
没有一个普遍认可的标准方法来做到这一点。有些人根本不允许 BST 存储重复项,基本上定义了这个问题。 (这就是您在将树用于 map 和集合时经常看到的)。其他实现可能将所有相同的键存储在同一个节点中,可能通过使用链表。其他人可能会说左子树包含较小的键,而右子树包含大于或等于节点自身键的键。
每种方法都有优点和缺点,您可以选择最适合您的用例的方法。
https://stackoverflow.com/questions/68207641/