哪个是可用于在Python中实现二进制树的最佳数据结构？

对于二进制搜索树类型的数据结构,我看到Big O表示法通常标记为O(logn).在日志中使用小写的"l",这是否意味着日志基数e(n)如自然对数所描述的那样？抱歉这个简单的问题,但我总是无法区分不同的隐含对数.

我最近意识到,虽然在我的生活中使用了BST,但我甚至都没有考虑过使用任何东西而是使用Inorder遍历(虽然我知道并且知道调整程序使用前/后顺序遍历是多么容易).

在意识到这一点之后,我拿出了一些旧的数据结构教科书,并寻找了预订和后序遍历的有用性背后的推理 - 但他们并没有说太多.

什么时候实际使用预订/后期订单的一些例子？什么时候比按顺序更有意义？

我正在为我正在进行的项目构建一个符号表.我想知道人们对可用于存储和创建符号表的各种方法的优点和缺点的看法.

我做了很多搜索,最常推荐的是二叉树或链表或哈希表.以上所有优点和缺点是什么？(在c ++中工作)

我对以下树的术语感到困惑,我一直在研究树,我无法区分这些树:

a)完整的二叉树

b)严格的二叉树

c)完整的二叉树

请帮我区分这些树.在数据结构中何时何地使用这些树？

可以使用哪些算法在控制台中绘制二叉树？树以C实现.例如,数字:2 3 4 5 8的BST将在控制台中显示为:

对于二叉树:没有必要考虑树节点值,我只对具有'N'节点的不同树拓扑感兴趣.

对于二进制搜索树:我们必须考虑树节点值.

我知道性能永远不会是黑白的,通常一个实现在X情况下更快,在Y情况下更慢等等,但一般来说 - B树比AVL或RedBlack-Trees快吗？它们比AVL树(甚至可能是RedBlack-trees？)要复杂得多,但它们更快(它们的复杂性是否得到回报)？

编辑:我还想补充一点,如果它们比等效的AVL/RedBlack树更快(就节点/内容而言) - 为什么它们更快？

.NET 4.0中是否有内置的二叉搜索树,还是需要从头开始构建这种抽象数据类型？

编辑

这具体是关于二叉搜索树,而不是一般的抽象数据类型"树".

我正在寻找计算AVL树中节点平衡的最佳方法.我以为我有它工作,但经过一些繁重的插入/更新,我可以看到它的工作正常(根本没有).

这是一个由两部分组成的问题,第一部分是如何计算子树的高度,我知道定义"节点的高度是从该节点到叶子的最长向下路径的长度".而我理解它,但我没有实现它.并且为了进一步混淆我这个引用可以在维基百科的树高上找到"传统上,值-1对应于没有节点的子树,而零对应于具有一个节点的子树."

而第二部分是得到一个子树的平衡因素,AVL树,我没有问题理解概念,"让你的高度L和R子树和减去R从L".这被定义为这样的事情:BALANCE = NODE[L][HEIGHT] - NODE[R][HEIGT]

在维基百科上阅读在描述插入到AVL树中的前几行中说:"如果平衡因子变为-1,0或1,那么树仍然是AVL形式,并且不需要旋转."

然后继续说,"如果平衡因子变为2或-2,那么植根于此节点的树是不平衡的,并且需要树旋转.最多需要单次或双次旋转来平衡树." - 我没有抓麻烦.

但是(是的,总有一个但是).

这是令人困惑的地方,文本说明"如果R的平衡因子为1,则意味着插入发生在该节点的(外部)右侧,需要左旋转".但是从理解的角度来看,正如我所引用的那样,如果平衡因素在[-1, 1]那之内,那么就没有必要进行平衡了吗？

我觉得我是如此接近抓概念,我已经得到了树旋转下来,实现正常的二叉搜索树,抓AVL树的边缘,但只是似乎缺少必要的顿悟.

编辑:代码示例比学术公式更受欢迎,因为我总是更容易在代码中掌握一些东西,但是非常感谢任何帮助.

编辑:我希望我能将所有答案都标记为"已接受",但对我而言,NIck的答案是第一个让我走"aha"的答案.