为什么 Avl 树的大小是 O(n)？
why is the size of an Avl tree O(n)?
AVL 树的所有操作只有 O(logn)，因为它是一棵平衡树。高度也是 O(logn) 那么为什么 AVL 树本身的大小是 O(n) 有人可以向我解释一下吗？我知道你必须计算左子树+1（对于根）+右子树以获得整个tree.Howevery的大小操作以获得例如右子树的大小是log（n）和logn + logn+1 不等于 O(n)
要计算树的大小，你将不得不遍历tree.Hence中的每个节点一次，如果树中有n个节点，遍历每个节点一次最终将导致时间复杂度为o( n).
当我们谈论时间复杂度或 space 复杂度时，我们指的是时间或 space 要求相对于输入大小的变化率。例如。当我们说 O(1) 时，我们的意思是无论输入的大小如何，时间（在时间复杂度的情况下）或 space（在 space 复杂度的情况下）都是常数。所以 O(1) not 表示 1 秒或 1 分钟。它只是意味着输入大小不变。如果您根据不同的输入大小绘制执行时间，您会得到一条水平线。 O(n) 或 O(log n) 的情况类似。
有了这个认识，我们来谈谈AVL树。 AVL树是一种平衡的二叉搜索树。因此，在树中搜索节点的平均时间复杂度为 O(log n)。请注意，要搜索节点，您不会访问树的每个节点（与 LinkedList 不同）。如果您必须访问每个节点，您会说时间复杂度为 O(n)。在 AVL 树的情况下，每次发现不匹配时，都会丢弃树的一半并继续搜索剩余的一半。
在最坏的情况下，您将在树的每一层进行一次比较，即等于树的高度，因此搜索时间复杂度为 O(log n)。左树的大小是 not O(log n).
关于大小，您确实需要 space 来存储每个节点。如果必须存储 1 个节点，则需要 1 个单元 space，对于 2 个节点，2 个单元，对于 3 个节点，3 个单元，依此类推。这个单位可以是任何 10 字节、1 KB、5 KB 的任何东西。 Thr 点是，如果你绘制计算机内存中输入的 space 要求与树的数量，你得到的只是一个从零开始的线性图。那是 O(n).
进一步澄清，在计算算法的时间或space复杂度时，如果复杂度为O(1 + log n + 4n + 2^n + 100)，我们称其为O( 2^n) 即我们取最大值，因为我们不是在计算绝对值，我们是在计算相对于输入大小的变化率，因此最大值才是最重要的。
如果说计算树的大小的算法的时间复杂度，你需要访问树中的每个节点。由于节点总数为n，因此将是O(n)。
AVL 树的所有操作只有 O(logn)，因为它是一棵平衡树。高度也是 O(logn) 那么为什么 AVL 树本身的大小是 O(n) 有人可以向我解释一下吗？我知道你必须计算左子树+1（对于根）+右子树以获得整个tree.Howevery的大小操作以获得例如右子树的大小是log（n）和logn + logn+1 不等于 O(n)
要计算树的大小，你将不得不遍历tree.Hence中的每个节点一次，如果树中有n个节点，遍历每个节点一次最终将导致时间复杂度为o( n).
当我们谈论时间复杂度或 space 复杂度时，我们指的是时间或 space 要求相对于输入大小的变化率。例如。当我们说 O(1) 时，我们的意思是无论输入的大小如何，时间（在时间复杂度的情况下）或 space（在 space 复杂度的情况下）都是常数。所以 O(1) not 表示 1 秒或 1 分钟。它只是意味着输入大小不变。如果您根据不同的输入大小绘制执行时间，您会得到一条水平线。 O(n) 或 O(log n) 的情况类似。
有了这个认识，我们来谈谈AVL树。 AVL树是一种平衡的二叉搜索树。因此，在树中搜索节点的平均时间复杂度为 O(log n)。请注意，要搜索节点，您不会访问树的每个节点（与 LinkedList 不同）。如果您必须访问每个节点，您会说时间复杂度为 O(n)。在 AVL 树的情况下，每次发现不匹配时，都会丢弃树的一半并继续搜索剩余的一半。
在最坏的情况下，您将在树的每一层进行一次比较，即等于树的高度，因此搜索时间复杂度为 O(log n)。左树的大小是 not O(log n).
关于大小，您确实需要 space 来存储每个节点。如果必须存储 1 个节点，则需要 1 个单元 space，对于 2 个节点，2 个单元，对于 3 个节点，3 个单元，依此类推。这个单位可以是任何 10 字节、1 KB、5 KB 的任何东西。 Thr 点是，如果你绘制计算机内存中输入的 space 要求与树的数量，你得到的只是一个从零开始的线性图。那是 O(n).
进一步澄清，在计算算法的时间或space复杂度时，如果复杂度为O(1 + log n + 4n + 2^n + 100)，我们称其为O( 2^n) 即我们取最大值，因为我们不是在计算绝对值，我们是在计算相对于输入大小的变化率，因此最大值才是最重要的。
如果说计算树的大小的算法的时间复杂度，你需要访问树中的每个节点。由于节点总数为n，因此将是O(n)。