为什么添加不平衡二进制搜索树O（n）？ [英] Why is add in unbalanced Binary Search Tree O(n)?

问题描述

这是从中添加二进制搜索树的实现BST添加

private IntTreeNode add(IntTreeNode root, int value) {
        if (root == null) {
            root = new IntTreeNode(value);
        } else if (value <= root.data) {
            root.left = add(root.left, value);
        } else {
            root.right = add(root.right, value);
        }

        return root;
    }

我明白为什么这在O（日志n）中运行。以下是我分析的方法。我们的树大小为n。多少次切割2次或半次切割会将该树缩小到1个大小。所以我们有n（1/2）^ x = 1，其中1/2表示每个半切。解决这个x，我们有log2（x），所以logn来自搜索。

这是一个演讲幻灯片从堆。

I understand why this runs in O(log n). Here's how I analyze it. We have a tree size of n. How many cuts of 2, or half cut, will reduce this tree down to a size of 1. So we have the expression n(1/2)^x = 1 where the 1/2 represents each half cut. Solving this for x, we have log2(x) so the logn comes from search.
Here is a lecture slide from Heap that discusses runtime for an unbalanced binary search.

我的问题是即使二叉搜索树是不平衡的，不一样的策略可以用于分析添加的运行时呢？你要做多少切割运行时不会是O（log n），而不是O（n）？如果是这样，有人可以显示为什么会是O（n）的数学？

My question is even if the binary search tree is unbalanced, wouldn't the same strategy work for analyzing the runtime of add? How many cuts you have to make. Wouldn't the runtime still be O(log n), not O(n)? If so, can someone show the math of why it would be O(n)?

推荐答案

使用不平衡的树： p>

With an unbalanced tree:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          ...

您的直觉将树切成一半，每次操作都不再适用。这个不平衡的树是不平衡二叉搜索树的最坏情况。要搜索列表底部的 10 ，您必须执行 10 操作，一个用于树中的每个元素。这就是为什么不平衡二叉搜索树的搜索操作是（n） - 这个不平衡二叉搜索树等同于一个链表。每个操作都不会切断树的一半 - 只是您已经访问过的一个节点。

Your intuition of cutting the tree in half with each operation no longer applies. This unbalanced tree is the worst case of an unbalanced binary search tree. To search for 10 at the bottom of the list, you must make 10 operations, one for each element in the tree. That is why a search operation for an unbalanced binary search tree is O(n) - this unbalanced binary search tree is equivalent to a linked list. Each operation doesn't cut off half the tree -- just the one node you've already visited.

这就是为什么专门版本的二叉搜索树，如红色 - 黑木树和AVL树很重要：它们保持足够平衡的树，以便所有操作 - 搜索，插入和删除 - 仍然是（日志n）。

That is why specialized versions of binary search trees, such as red-black trees and AVL trees are important: they maintain trees that are balanced well enough so that all operations - search, insert, delete -- are still O(log n).

这篇关于为什么添加不平衡二进制搜索树O（n）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！