为什么不平衡的二叉搜索树为O（n）为补充的吗？ [英] Why is add in unbalanced Binary Search Tree O(n)?

问题描述

这是加入二叉搜索树从 BST实施添加

This is the implementation of add in Binary Search Tree from BST Add

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（log n）的。以下是我分析它。我们有N个树的大小。 2，或半切多少削减，可以减少该树上下来为1的尺寸所以我们有恩pression N（1/2）^ X = 1，其中的1/2重presents每个半切。解决这个对于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)?

推荐答案

通过一个不平衡的树：

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

您的每个操作切割树一半的直觉不再适用。这种不平衡的树是一种不平衡的二进制搜索树的最坏情况。要搜索 10 在列表的底部，你必须让 10 的操作，一个是树中的每个元素。这就是为什么一个不平衡的二分搜索树的搜索操作为 0 的（正） - 此不平衡叉查找树相当于一个链表。每个操作都不会切断一半的树 - 只是你已经访问了一个节点

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树是很重要的：他们认为是平衡的不够好树，使所有业务 - 搜索，插入，删除 - 依然的 0 的（log 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屋！