二叉树问题

Question

目前正在学习考试，并通读一些笔记时，我有几个问题。

1. 我知道二叉搜索树的高度是Log（n）。这是否意味着深度也是Log（n）？

2. 什么是具有n个节点的完整二叉树中节点的最大深度？这与第一个问题有关;如果二叉树的高度是Log（n），那么最大深度也是Log（n）？

3. 我知道在二叉搜索树中搜索节点的时间复杂度是O（Log（n）），据我所知。但是，我读到最坏情况下的时间复杂度是O（N）。在什么情况下需要O（N）时间才能找到一个元素？

4. 这是一个优先队列/堆问题。在我的讲义中，它说以下语句：

   如果我们使用优先队列的数组，排队需要O（1），排队需要O（n）。在排序的数组中，en-queue需要O（N），并且取消队列需要O（1）。

   我很难理解这一点。谁能解释一下？

对不起，所有的问题，真的需要一些这些主题的一些清晰。

Answer 1

警告：我是有点生疏，但在这里不用...

高度和二叉树的深度是同义 - 更多或更少。高度是沿着从根到叶的任何路径的最大深度。但是，当你遍历树时，你有一个当前深度的概念。根节点的深度为0，其子节点的深度为1，其子孙的深度为2.如果我们在这里停止，树的高度为3，但是我们访问的最大深度为2，否则在谈论时经常互换树整体。

在我们谈到更多问题之前，需要注意的是二叉树有各种不同的风格。平衡或不平衡。使用完美平衡的树，除最大高度以外的所有节点都将使其左/右链接非空。例如，在树中有n个节点，令n = 1024。完美平衡的高度是10（例如1024 == 2^10）的log2（n）。

当你搜索一个完美的平衡树，搜索为 O（LOG 2（N）），因为从根节点开始，你选择跟随左或右，并在每次做的时候，你消除1/2个节点。在这种有1024个元素的树中，深度为10，你做出10个这样的左/右判定。

当您添加新节点时，大多数树算法会即时重新平衡树（例如AVL或RB（红黑色））树。所以，你总是或多或少地得到一棵完美平衡的树。

但是...

让我们考虑一个非常糟糕的算法。当你添加一个新节点时，它只会将它附加到最大深度的子节点上的左侧链接[或新节点变成新的根节点]。这个想法是快速追加，并且“我们稍后会重新平衡”。

如果我们搜索这个“坏”树，如果我们已经添加了n个节点，树看起来像使用父链接和左链接的双链表[记住所有正确的链接都是NULL]。这是线性时间搜索或O（n）。

我们故意这样做了，但它仍然可以在某些树算法和/或数据组合的情况下发生。也就是说，数据是自然放置在左侧链接上的，因为这是基于算法放置函数放置它的正确位置。

优先级队列就像常规队列一样，除了每条数据都有一个与之相关的优先级号。

在一个普通的队列中，你只需按下/追加到最后。当你离队时，你从前面移动/弹出。你从来没有需要在中间插入任何东西。因此，入队和出队都是O（1）操作。 O（n）来自这样一个事实，即如果必须在数组中间插入一个数据，则必须“分开水域”为要插入的元素留出空间。例如，如果您需要在第一个元素[array [0]]之后插入，则会将新元素放置在array [1]处，但首先必须将array [1]移动到array [2]，数组[2]到数组[3]，...对于n的数组，这是O（n）努力。

从数组中删除元素时，它是相似的，但是相反。如果你想删除数组[1]，你抓住它，那么你必须通过数组[1] =数组[2]，数组[2] =数组[3]，“...”再次，O（n）操作。

在排序数组中，您只需弹出结尾。这是你想要的。因此O（1）。要添加元素，请将其插入正确的位置。如果你的数组是1,2,3,7,9,12,17并且你想添加6，那么数组[4]就是新的值，你必须移动7,9,12,17作为以上。

优先级队列只是附加到数组，因此O（1）。但要找到正确的出列元素，可以扫描数组数组[0]，数组[1]，......记住给定优先级的第一个元素位置，如果您发现优先级更高，那么您应该记住这一点。当你达到目的时，你知道你需要哪个元素，说它是j。现在你必须从数组中删除j，并且如上所述的O（n）操作。

它比所有这些稍微复杂，但不是两个多。