Как узнать, существует ли узел в двоичном дереве или нет (по индексу, а не по значению)? - PullRequest
Новая
       33

Как узнать, существует ли узел в двоичном дереве или нет (по индексу, а не по значению)?

0 голосов
/ 16 февраля 2019

Дано полное двоичное дерево, в котором узлы индексируются от 1 до N (индекс 1 - это корень, N - количество узлов в дереве).Можем ли мы найти, существует ли узел с определенным индексом в дереве или нет, за O (logN) сложность времени? 

How is the indexing done?
for a node say it has      index x
                          /        \
             node.left is 2*x    node.right is 2*x+1

Ниже я написал код, который работает в O (N)

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

Можно ли достичь этой цели за O (logN) сложность времени, используя тот факт, что это полное двоичное дерево? 

##TreeNode object
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

##findIndex
def findIndex(root,index,target):
    if root == None:
        return False
    if index == target:
        return True

    leftSide = findIndex(root.left,2*index,target)
    rightSide = findIndex(root.right,2*index+1,target)

    return (leftSide or rightSide)

##Create tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

"""
For the sake of simplicity, 
the tree node values are the same as their index.
                1
               /  \
             2     3
            / \  
           4   5
"""

##call findIndex

## findIndex(root, startIndex, targetIndex) 

print findIndex(root,1,1) ## returns True
print findIndex(root,1,8) ## returns False

1 Ответ

0 голосов
/ 28 марта 2019

Поскольку мы уже знаем, что левый узел - 2 * n, а правый узел - 2 * n + 1. Позволяет сначала начать с заданного индекса на входе и найти путь.Например, если у нас был индекс 10, то мы знаем, что 10 должно быть слева от 5, что, в свою очередь, должно быть справа от 2, то есть слева от корня или 1. Таким образом, путь слева, справа,оставил.Теперь просто проследуйте по этому пути в двоичном дереве до тех пор, пока его ноль, если узел существует, вернет true, иначе false.

...