Анализируя BST является сбалансированным кодом - PullRequest
Новая
       6

Анализируя BST является сбалансированным кодом

0 голосов
/ 24 мая 2018

Я просматривал этот код Python, чтобы проверить, сбалансировано ли дерево двоичного поиска.Тем не менее, мне было интересно, если кто-нибудь может объяснить, как

height = max(left_height, right_height) + 1 вступает в игру.Как эта строка кода работает для расчета высоты.И наконец, как работает эта 

is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

рекурсия стека, потому что когда вызывается is_balanced (cur_node.left), он вызывается снова, когда вызывается второй TreeNode.is_balanced (cur_node.right).

У меня проблемы с отслеживанием трассировки стека для этого.

Вот весь код: 

def is_balanced(cur_node) :
            if (not cur_node) :
                height = 0
                return True, height

            is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
            is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

            #To get the height of the current node, we find the maximum of the  
            #left subtree height and the right subtree height and add 1 to it
            height = max(left_height, right_height) + 1

            if (not is_left_balanced or not is_right_balanced):
                return False, height

            #If the difference between height of left subtree and height of
            #right subtree is more than 1, then the tree is unbalanced
            if (abs(left_height - right_height) > 1):
                return False, height

            return True, height

1 Ответ

0 голосов
/ 24 мая 2018

При работе с рекурсивными проблемами вы всегда должны обращать внимание на базовые случаи.В этой программе есть только один базовый случай: пустое дерево, которое имеет тривиально достижимую высоту 1 и по определению сбалансировано.Теперь предположим, что дерево не сбалансировано, если его самая высокая половина имеет высоту более 1 плюс высоту его второй половины (то есть его самая высокая половина выше как минимум на два уровня), или если одно из его поддеревьев не сбалансировано, томы получаем рекурсивный способ вычисления этого.

Сначала вернем 0 и True для тривиально сбалансированного (пустого) дерева.Мы получили наш базовый случай.

Во-вторых, если любая из половин не сбалансирована, то дерево не сбалансировано.Это проверяется для каждого поддерева, и, таким образом, рекурсия будет продолжаться до тех пор, пока не будет найдено пустое дерево, откуда оно начнет возвращаться (представьте себе случай дерева только с одним уровнем, одним узлом. Представьте, как будет выполняться код, и вы, вероятно,быть в состоянии экстраполировать оттуда).

Наконец, если каждое поддерево сбалансировано (это третий случай, так как мы уже продвинулись так далеко в программу), тогда единственный способ, которым дерево не сбалансировано, - это если один изего поддеревья выше других более чем на один уровень.Мы просто проверяем это и возвращаем противоположное значение.

Я надеюсь, что это помогло вам понять, не стесняйтесь задавать мне любые другие вопросы в противном случае!

...