我编辑的二叉搜索树 get_size 方法的时间复杂度

Question

我正在努力寻找我在二叉搜索树中创建的 get_size 方法的时间复杂度，因为存在多个 conditions.Here 的多重递归是代码

`class Node:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.right = right
        self.left = left

    def __str__(self):
        return str(self.data)

我创建了节点 class 来存储数据，然后我创建了 BST 函数，它确实有效，但问题是每个函数的时间复杂度应该是函数中的 log n，但我使用了 if elif else 和双递归它是否同时影响运行时间如果它影响为什么如果它不影响为什么

class BST:
    def __init__(self):
        self.root = None

    def add(self, value, x=None):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        if x is None:
            main_node = self.root
        else:
            main_node = x

        if value > main_node.data:
            if main_node.left is None:
                main_node.left = new_node
                return True
            else:
                return self.add(value, main_node.left)
        elif value == main_node.data:
            return False
        elif value < main_node.data:
            if main_node.right is None:
                main_node.right = new_node
                return True
            else:
                return self.add(value, main_node.right)

    def get_size(self, x=None):
        if self.root is None:
            return 0
        if x is None:
            main_node = self.root
        else:
            main_node = x
        if main_node.left is not None and main_node.right is not None:
            return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)
        elif main_node.left is None and main_node.right is None:
            return 1
        else:
            if main_node.left is not None:
                return 1 + self.get_size(main_node.left)
            else:
                return 1 + self.get_size(main_node.right)`

Answer 1

要确定复杂性，有助于将您的功能分解并分别分析不同的部分。

从基本情况开始，复杂度为 O(1)。

if self.root is None:
    return 0

elif main_node.left is None and main_node.right is None:
    return 1

但是，随着您开始递归，这些基本情况会加起来。让我们看一下递归调用之一：

if main_node.left is not None and main_node.right is not None:
    return 1 + self.get_size(main_node.left) + self.get_size(main_node.right)

在最简单的树中，main_node的左右children都是叶子，那么对get_size()的这2次调用将不会再递归，导致两个O (1)操作。但是，如果任一节点有 children，那么我们将对 get_size() 进行额外调用，使 get_size() 大于 O(1)。如果左边的 child 有 children，但那些 children 是叶子，那么我们将再次调用 get_size() 两次，每次都是 O(1) 调用。

如果我们对函数中每个可能的 if/else 语句重复此分析，我们将看到对于每个存在的 child，我们将只为它调用一次 get_size()一次。因此，我们的整体复杂度是O(n)。

我编辑的二叉搜索树 get_size 方法的时间复杂度

Time complexity of binary search tree get_size method which i edited

recursion

big-o

binary-tree

time-complexity

binary-search-tree