Ruby实现的Binary Tree是否正确？构建逻辑求技术验证

嘿，我来帮你拆解下这两个问题～

你的Ruby实现是否正确？ #

首先可以放心，你的代码逻辑是完全没问题的！

你之前用C指针实现二叉树，核心是通过指针关联父节点和子节点；而Ruby里没有指针，用的是对象引用来做同样的事——比如node.left = Node.new(value, node)这行代码，就是让当前节点的left实例变量指向新创建的子节点，本质和C里的指针赋值逻辑一致，只是Ruby帮你处理了内存管理，不用手动new/delete而已。

从功能上看，你逐个遍历数组元素插入的方式，能正确构建出二叉搜索树，测试运行正常也符合预期。不过可以提两个小细节：

• build_tree方法最后返回@root其实没必要，因为在add_child的第一个分支（@root.nil?）里已经给@root赋值了，方法执行完@root已经是有效的根节点；
• 你自己也注意到了没处理重复值，如果需要支持重复值，可以在add_child里加一个value == node.value的分支，比如选择跳过、插入到左子树或者右子树（取决于你想要的业务规则）。

为什么有多种build实现？不同方式的适用场景？ #

你观察到的不同build方式，核心是为了平衡实现复杂度和树的性能，各自有对应的适用场景：

1. 你现在用的「逐个插入」方式 #

• 适用场景：无序数组，或者对树的平衡性没有要求的场景。
• 优点：实现简单，不管数组有没有排序都能正常构建出二叉搜索树；
• 缺点：如果输入的是有序数组，这种方式会把树构建成一个单向链表（比如从小到大的数组，每个新元素都插在右子树），树的高度等于数组长度，此时查询、插入的时间复杂度会从二叉搜索树理想的O(logn)退化成O(n)，性能大打折扣。

2. 「从数组中点开始构建」的方式 #

• 适用场景：已经排序的数组。
• 原理：利用有序数组的特性，取中间元素作为根节点，然后把数组分成左右两部分，递归构建左右子树，这样能保证树的左右子树高度差不超过1，也就是平衡二叉搜索树；
• 优点：构建出来的树高度是log₂(n)级别，查询、插入的效率能稳定在O(logn)；
• 缺点：必须依赖有序数组，如果数组无序，这种方式无法构建正确的二叉搜索树，而且需要先对数组排序（如果原数组无序的话）。

简单总结：两种方式没有绝对的好坏，只是适用场景不同——如果你的输入数组大概率是无序的，或者不想额外做排序操作，用你现在的实现就很好；如果输入是有序数组，或者需要最优的查询性能，就用中点构建的方式。

内容的提问来源于stack exchange，提问作者msmith1114