二叉树问题
Binary Tree Questions
目前正在备考，边看笔记边想了几个问题。
我知道二叉搜索树的高度是Log(n)。这是否意味着深度也是 Log(n)？
n个节点的满二叉树中一个节点的最大深度是多少？这与第一个问题有关；如果二叉树的高度是 Log(n)，那么最大深度是否也是 Log(n)？
我知道在二叉查找树中查找一个节点的时间复杂度是O(Log(n))，这个我理解。但是，我读到最坏情况下的时间复杂度是 O(N)。什么情况下找一个元素需要O(N)的时间？
这是一个优先级队列/堆问题。在我的讲义中，它说了以下语句：
If we use an array for Priority Queues, en-queuing takes O(1) and de-queuing takes O(n). In a sorted Array, en-queue takes O(N) and de-queue takes O(1).
我很难理解这一点。谁能解释一下？
抱歉提出所有问题，确实需要澄清其中的一些主题。
警告：我有点生疏，但是这里...
二叉树的高度和深度或多或少是同义词。高度是从根到叶的任何路径上的最大深度。但是，当你遍历一棵树时，你就有了当前深度的概念。根节点的深度为 0，其子节点的深度为 1，其孙节点的深度为 2。如果我们停在这里，树的高度为 3，但最大深度 [我们访问过] 为 2。否则，在讨论时它们经常互换整棵树。
在我们回答您的更多问题之前，请务必注意二叉树有多种形式。平衡或不平衡。对于完美平衡的树，除了最大高度的节点之外的所有节点都将具有它们的 left/right links 非空。例如，树中有 n 个节点，令 n = 1024。高度完全平衡是 log2(n)，它是 10（例如 1024 == 2^10）。
当你搜索一棵完全平衡的树时，搜索 是 O(log2(n)) 因为从根节点开始，你选择向左或向右，并且每次这样做，都会消除 1/2 的节点。在这样一棵有 1024 个元素的树中，深度为 10，你做出 10 个这样的 left/right 决定。
大多数树算法，当你添加一个新节点时，会动态地重新平衡树（例如 AVL 或 RB（红黑））树。所以，你或多或少总是得到一棵完美平衡的树。
但是...
让我们考虑一个非常糟糕的算法。当你添加一个新节点时，它只是将它附加到深度最大的子节点的左侧 link [或者新节点成为新的根节点]。想法是快速追加，"we'll rebalance later".
如果我们搜索这棵 "bad" 树，如果我们添加了 n 个节点，则该树看起来像一个使用父 link 和左 link [记住所有正确的 links 都是 NULL]。这是线性时间搜索或 O(n)。
我们是故意这样做的，但是对于某些树算法 and/or 数据组合，它仍然会发生。也就是说，数据会自然地放置在左侧 link 因为这是根据算法的放置函数放置它的正确位置。
优先级队列类似于常规队列，只是每条数据都有一个与之关联的优先级编号。
在普通队列中，您只需 push/append 到末尾即可。当你出队时，你从前面shift/pop。您永远 不需要在中间插入任何东西。因此，入队和出队都是 O(1) 操作。
O(n) 来自这样一个事实，如果你必须在数组的中间插入，你必须 "part the waters" 为你想要的元素制作 space插入。例如，如果您需要在第一个元素 [即数组 [0]] 之后插入，您会将新元素放置在数组 [1] 处，但首先您必须将数组 [1] 移动到数组 [2]， array[2] 到 array[3], ... 对于 n 的数组，这是 O(n) 的努力。
从数组中删除一个元素时，它是类似的，但相反。如果你想移除 array[1]，你抓住它，那么你必须 "close the gap" 由 array[1] = array[2], array[2] = array[3], ...又是一次 O(n) 操作。
在排序数组中，您只需从末尾弹出。已经是你想要的了因此 O(1)。要添加一个元素，它会插入到正确的位置。如果你的数组是 1,2,3,7,9,12,17 并且你想添加 6，这是数组 [4] 的新值，你必须将 7,9,12,17 移开作为以上。
优先级队列只是附加到数组，因此 O(1)。但是要找到要出列的正确元素，您可以扫描数组 array[0]、array[1]，...记住给定优先级的第一个元素位置，如果找到更好的优先级，您会记住它。当你到达终点时，你知道你需要哪个元素，比如说它是 j。现在你必须从数组中删除 j，并且 O(n) 操作如上所述。
它比所有这些稍微复杂一些，但不会复杂太多。
目前正在备考，边看笔记边想了几个问题。
我知道二叉搜索树的高度是Log(n)。这是否意味着深度也是 Log(n)？
n个节点的满二叉树中一个节点的最大深度是多少？这与第一个问题有关；如果二叉树的高度是 Log(n)，那么最大深度是否也是 Log(n)？
我知道在二叉查找树中查找一个节点的时间复杂度是O(Log(n))，这个我理解。但是，我读到最坏情况下的时间复杂度是 O(N)。什么情况下找一个元素需要O(N)的时间？
这是一个优先级队列/堆问题。在我的讲义中，它说了以下语句：
If we use an array for Priority Queues, en-queuing takes O(1) and de-queuing takes O(n). In a sorted Array, en-queue takes O(N) and de-queue takes O(1).
我很难理解这一点。谁能解释一下？
抱歉提出所有问题，确实需要澄清其中的一些主题。
警告：我有点生疏，但是这里...
二叉树的高度和深度或多或少是同义词。高度是从根到叶的任何路径上的最大深度。但是，当你遍历一棵树时，你就有了当前深度的概念。根节点的深度为 0，其子节点的深度为 1，其孙节点的深度为 2。如果我们停在这里，树的高度为 3，但最大深度 [我们访问过] 为 2。否则，在讨论时它们经常互换整棵树。
在我们回答您的更多问题之前，请务必注意二叉树有多种形式。平衡或不平衡。对于完美平衡的树，除了最大高度的节点之外的所有节点都将具有它们的 left/right links 非空。例如，树中有 n 个节点，令 n = 1024。高度完全平衡是 log2(n)，它是 10（例如 1024 == 2^10）。
当你搜索一棵完全平衡的树时，搜索 是 O(log2(n)) 因为从根节点开始，你选择向左或向右，并且每次这样做，都会消除 1/2 的节点。在这样一棵有 1024 个元素的树中，深度为 10，你做出 10 个这样的 left/right 决定。
大多数树算法，当你添加一个新节点时，会动态地重新平衡树（例如 AVL 或 RB（红黑））树。所以，你或多或少总是得到一棵完美平衡的树。
但是...
让我们考虑一个非常糟糕的算法。当你添加一个新节点时，它只是将它附加到深度最大的子节点的左侧 link [或者新节点成为新的根节点]。想法是快速追加，"we'll rebalance later".
如果我们搜索这棵 "bad" 树，如果我们添加了 n 个节点，则该树看起来像一个使用父 link 和左 link [记住所有正确的 links 都是 NULL]。这是线性时间搜索或 O(n)。
我们是故意这样做的，但是对于某些树算法 and/or 数据组合，它仍然会发生。也就是说，数据会自然地放置在左侧 link 因为这是根据算法的放置函数放置它的正确位置。
优先级队列类似于常规队列，只是每条数据都有一个与之关联的优先级编号。
在普通队列中，您只需 push/append 到末尾即可。当你出队时，你从前面shift/pop。您永远 不需要在中间插入任何东西。因此，入队和出队都是 O(1) 操作。
O(n) 来自这样一个事实，如果你必须在数组的中间插入，你必须 "part the waters" 为你想要的元素制作 space插入。例如，如果您需要在第一个元素 [即数组 [0]] 之后插入，您会将新元素放置在数组 [1] 处，但首先您必须将数组 [1] 移动到数组 [2]， array[2] 到 array[3], ... 对于 n 的数组，这是 O(n) 的努力。
从数组中删除一个元素时，它是类似的，但相反。如果你想移除 array[1]，你抓住它，那么你必须 "close the gap" 由 array[1] = array[2], array[2] = array[3], ...又是一次 O(n) 操作。
在排序数组中，您只需从末尾弹出。已经是你想要的了因此 O(1)。要添加一个元素，它会插入到正确的位置。如果你的数组是 1,2,3,7,9,12,17 并且你想添加 6，这是数组 [4] 的新值，你必须将 7,9,12,17 移开作为以上。
优先级队列只是附加到数组，因此 O(1)。但是要找到要出列的正确元素，您可以扫描数组 array[0]、array[1]，...记住给定优先级的第一个元素位置，如果找到更好的优先级，您会记住它。当你到达终点时，你知道你需要哪个元素，比如说它是 j。现在你必须从数组中删除 j，并且 O(n) 操作如上所述。
它比所有这些稍微复杂一些，但不会复杂太多。