完全退化的二叉树比链表差吗？
Is a completely degenerate binary tree worse than a linked list?
考虑到时间和space哪个更糟？链表还是完全退化的二叉树？
最多只能说：链表永远不会比退化的二叉树差。它实际上更好吗？可能没那么多。
让我们比较一下：
- 链表
item -> item -> item -> item -> item -> item -> item ->NUL
- 退化二叉树
item -> item -> item -> item -> item -> item -> item ->NUL
\ \ \ \ \ \ \ \ \ \ \
NUL NUL NUL NUL NUL NUL NUL NUL NUL NUL NUL
Space
注意前面图中的箭头是指针；因此，箭头占用的内存 space 是指针的大小，可能最多为 64 位。项目的大小取决于项目本身，如果它是一个字符，则可能为 8 位；如果它是具有大量数据的复杂 class 的对象，则可能会很大。
- 如果项包含在节点中，则链表的大小为
n * (sizeof(item) + sizeof(ptr))，如果节点包含指向项的指针，则链表的大小为 n * (sizeof(item) + 2 * sizeof(ptr))。
- 退化二叉树的大小是
n * (sizeof(item) + 2 * sizeof(ptr)) 或 n * (sizeof(item) + 3 * sizeof(ptr))，同样取决于节点是直接包含项还是指向项的指针。
假设一个项目的大小至少与指针的大小一样大是非常合理的。更准确地说：
- 退化二叉树的大小是链表大小的两倍，如果项目是整数使用大约与指针一样多space；
- 如果项与指针相比非常大，退化二叉树的大小仅比链表的大小大一个可以忽略不计的因素。
如果你是一个理论家，只关心O( )，那么1和2之间的一个因素不会影响这个O( )，你可以认为两者是等价的。如果你是现实世界中的真人，并且关心内存中实际使用的 space，那么退化二叉树可能会占用两倍的内存，这可能是一个问题。
时间
遍历退化二叉树类似于遍历链表，除了探索虚拟叶子会浪费一些时间。究竟损失了多少时间？这取决于确切的算法，但假设存在一个因素似乎是合理的，可忽略或不存在。使用退化二叉树的算法会比链表慢。同样，这不会影响 O( )，但在现实世界中，这意味着您可能花费 2μs 而不是 1μs，或 2s 而不是 1s，或 1h 而不是 30min，等等
请注意，当今最能减慢处理器速度的事情之一是错误猜测的条件。在遍历列表时，需要在循环的每次迭代中测试指向下一个元素的指针，以回答“我们完成了吗？或者是否有下一个元素？”的问题。当用链表执行程序时，在除最后一次之外的大多数迭代中，处理器都会正确地猜测“有下一个元素”，这是一个巨大的时间增益。当使用退化二叉树执行程序时，处理器可能有一半的时间猜错，因为一半的指针是 NUL，一半不是。这可能会浪费大量时间。
结论
这是一个很好的猜测，链表并不比退化的二叉树差，但它们到底好多少很难说，而且是高度间接的。 Space 可能不是问题。时间可能会很明显，所以如果可以使用链表就不要使用退化二叉树；但是如果出于某种原因在大多数情况下你需要使用二叉树，并且在少数情况下碰巧二叉树退化了，不要对它有压力，也不要试图通过用链接替换它来过度优化列表。
考虑到时间和space哪个更糟？链表还是完全退化的二叉树？
最多只能说：链表永远不会比退化的二叉树差。它实际上更好吗？可能没那么多。
让我们比较一下：
- 链表
item -> item -> item -> item -> item -> item -> item ->NUL
- 退化二叉树
item -> item -> item -> item -> item -> item -> item ->NUL
\ \ \ \ \ \ \ \ \ \ \
NUL NUL NUL NUL NUL NUL NUL NUL NUL NUL NUL
Space
注意前面图中的箭头是指针；因此，箭头占用的内存 space 是指针的大小，可能最多为 64 位。项目的大小取决于项目本身，如果它是一个字符，则可能为 8 位；如果它是具有大量数据的复杂 class 的对象，则可能会很大。
- 如果项包含在节点中，则链表的大小为
n * (sizeof(item) + sizeof(ptr))，如果节点包含指向项的指针，则链表的大小为n * (sizeof(item) + 2 * sizeof(ptr))。 - 退化二叉树的大小是
n * (sizeof(item) + 2 * sizeof(ptr))或n * (sizeof(item) + 3 * sizeof(ptr))，同样取决于节点是直接包含项还是指向项的指针。 假设一个项目的大小至少与指针的大小一样大是非常合理的。更准确地说： - 退化二叉树的大小是链表大小的两倍，如果项目是整数使用大约与指针一样多space；
- 如果项与指针相比非常大，退化二叉树的大小仅比链表的大小大一个可以忽略不计的因素。 如果你是一个理论家，只关心O( )，那么1和2之间的一个因素不会影响这个O( )，你可以认为两者是等价的。如果你是现实世界中的真人，并且关心内存中实际使用的 space，那么退化二叉树可能会占用两倍的内存，这可能是一个问题。
时间
遍历退化二叉树类似于遍历链表，除了探索虚拟叶子会浪费一些时间。究竟损失了多少时间？这取决于确切的算法，但假设存在一个因素似乎是合理的，可忽略或不存在。使用退化二叉树的算法会比链表慢。同样，这不会影响 O( )，但在现实世界中，这意味着您可能花费 2μs 而不是 1μs，或 2s 而不是 1s，或 1h 而不是 30min，等等
请注意，当今最能减慢处理器速度的事情之一是错误猜测的条件。在遍历列表时，需要在循环的每次迭代中测试指向下一个元素的指针，以回答“我们完成了吗？或者是否有下一个元素？”的问题。当用链表执行程序时，在除最后一次之外的大多数迭代中，处理器都会正确地猜测“有下一个元素”，这是一个巨大的时间增益。当使用退化二叉树执行程序时，处理器可能有一半的时间猜错，因为一半的指针是 NUL，一半不是。这可能会浪费大量时间。
结论
这是一个很好的猜测，链表并不比退化的二叉树差，但它们到底好多少很难说，而且是高度间接的。 Space 可能不是问题。时间可能会很明显，所以如果可以使用链表就不要使用退化二叉树；但是如果出于某种原因在大多数情况下你需要使用二叉树，并且在少数情况下碰巧二叉树退化了，不要对它有压力，也不要试图通过用链接替换它来过度优化列表。