二叉搜索树问题

Question

我正在考虑实现二叉搜索树。我已经实现了一些非常基本的操作，例如搜索，插入，删除。

请分享您的经验，我可以在二叉搜索树上执行所有其他操作，以及在任何给定情况下每次都需要执行一些实时操作（基本）..我希望我的问题很明确..

谢谢。

Answer 1

至少，二叉搜索树应该有插入，删除和搜索操作。任何其他操作将取决于你打算如何处理你的树，尽管一些通用的建议是：返回给定节点的父节点，查找给定节点的左侧和右侧子节点，返回根节点，预先排序，中间排序和后序遍历，以及广度优先遍历。

Answer 2

尝试遍历操作（例如，按顺序将树中的元素作为List返回），并确保在插入/删除元素时树保持平衡。

Answer 3

如果这是功课，祝你好运！

如果这是好奇，玩得开心！

如果你想要在生产代码中实现这一点，甚至不知道基本操作，不要这样做！

http://www.boost.org/doc/libs/1_38_0/boost/graph/detail/array_binary_tree.hpp

Answer 4

如果你真的只是想的东西的清单可能有用或有趣的实现...

1. 反向树一切的秩序。这是O（N）我想？
2. Subtree，x和y之间的元素作为二叉搜索树本身 - 应该是O（log N）我认为？
3. 最小，最大？是的，微不足道，但我没有想法！

Answer 5

你可能想看看返回树的不同方式：

• 深度优先（打算一路下跌的一个分支和备份，重复）
• 在顺序（在树的周围）
• 级别顺序（每个级别如图所示）
• 作为平面数组返回。

如果您感觉特别冒险，可以采用数组并将其作为树导入。有一个特定的格式，这就像（1（2（3）），（5） - 这个例子是不平衡的，但你得到的想法，它在维基百科上

Answer 6

你可能也想执行旋转操作A rotation在不改变元素顺序的情况下更改结构，通常用于平衡树（以确保叶子全部接近相同深度），也可用于将根改为一个给定的元素，如果你知道它会更频繁地出现在搜索中。

我的ASCII艺术不是很大，但是旋转可以把这个树：

 f 
    d  g 
    b e   
a c 

成树：

 d 
    b  f 
    a c e g 

第二棵树被平衡将使搜索f和g慢，并且在e保持不变的情况下更快地搜索d，a，b，c。

Answer 7

我想我看过某处“地图”操作。当您用单调函数更改树的所有元素时。即（f（x + dx）> = f（x））或始终下降（f（x + dx）< = f（x））的函数。在一种情况下，您需要将该函数应用于其他节点，您还需要镜像树（交换“左”和“右”节点），因为结果值的顺序将被颠倒。