java - 在二叉搜索树中处理相同的数据

Question

我正在自学数据结构，目前正在研究二叉搜索树。我很好奇如果您有相同的数据，您将如何对树进行排序。例如说我的数据由[4,6,2,8,4,5,7,3].

1. 我将 4 设置为根元素
2. 把 6 放在它的右边
3. 把 2 放在 4 的左边
4. 把 8 放在 6 的右边

然后我到了 4 我应该把它放在哪里4=4？向左还是向右？

选项1

选项#2

其中一个是正确的还是两者都错了？如果他们都错了，你能告诉我他们应该如何排序。谢谢！

Answer 1

通常二叉树不允许数据重复。如果您进行自定义实现，则可以存储元素计数。Java 中的 TreeSet 就是一个例子——它只包含唯一的元素。

实际上，您列出的案例破坏了树的整个结构。搜索操作现在看起来很奇怪，并且无法使用O(ln n)执行。在最坏的情况下需要O(n)，所以你失去了这个数据结构的所有好处。

Answer 2

如果这是一个排序树，那么无论哪种方式，您所拥有的都可以正常工作；最后，您将进行树遍历并转储数据。

如果这是一个搜索树，那么一旦遇到额外的（冗余）数据，我就会删除它；“它存在”。您确实说过这是一个搜索树，虽然并不理想，但它实际上并没有损坏 - 如果您搜索“4”，您将简单地捕获根节点（在这种情况下），并且永远不会低于该根节点以查看任何其他“4”。它不是最佳的，周围有所有额外的#。

无论您选择哪种方式，都会有最好的情况和最坏的情况；不要太担心左/右决定 - 通常没关系。如果您对已知数据流中的细节有扎实的掌握，您就可以针对该特定情况做出最佳决策。