Двунаправленные деревья бинарного поиска?

Question

Я пытался реализовать BST. На данный момент он добавляет только ключи в соответствии со свойством BST (Left-Lower, Right-Bigger). Хотя я реализовал это по-другому.

Вот как я думаю, что BST должны быть

Одиночное направление BST

Как я реализовал свой BST

Двунаправленный BST

Вопрос в том, является ли это правильной реализацией BST? (Как я вижу в двухстороннем BST, было бы легче искать, удалять и вставлять)

import pdb; 
class Node:
    def __init__(self, value):
        self.value=value
        self.parent=None
        self.left_child=None
        self.right_child=None

class BST:

    def __init__(self,root=None):
        self.root=root

    def add(self,value):
        #pdb.set_trace()
        new_node=Node(value)
        self.tp=self.root                                                   
        if self.root is not None:                                         
                while True:
                    if self.tp.parent is None:
                        break
                    else:
                        self.tp=self.tp.parent
                                                                            #the self.tp varible always is at the first node.
                while True:
                    if new_node.value >= self.tp.value :

                        if self.tp.right_child is None:
                            new_node.parent=self.tp
                            self.tp.right_child=new_node
                            break
                        elif self.tp.right_child is not None:
                            self.tp=self.tp.right_child
                            print("Going Down Right")
                            print(new_node.value)
                    elif new_node.value < self.tp.value :
                        if self.tp.left_child is None:
                            new_node.parent=self.tp
                            self.tp.left_child=new_node
                            break
                        elif self.tp.left_child is not None:
                            self.tp=self.tp.left_child
                            print("Going Down Left")
                            print(new_node.value)
        self.root=new_node



newBST=BST()
newBST.add(9)
newBST.add(10)
newBST.add(2)
newBST.add(15)
newBST.add(14)
newBST.add(1)
newBST.add(3)

Редактировать: я использовал циклы while вместо рекурсии. Может кто-нибудь пояснить, почему использование циклов while вместо рекурсии является плохой идеей в данном конкретном случае и в целом?

Answer 1

BST с родительскими ссылками используются время от времени.

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

Становится удобным использовать указатель на узел для представления позиции в дереве вместо полного пути, даже когдадерево содержит дубликаты, и эта позиция остается действительной, поскольку в другом месте выполняются обновления или удаления.

В абстрактном типе данных эти свойства облегчают, например, предоставление итераторов, которые не аннулируются мутациями.

Answer 2

Вы не описали, как вы получаете что-либо с указателем родителя. Алгоритм, который заботится о перемотке на родительский узел, будет делать это путем обхода стека вызовов.

Я был там - в своем классе структур данных я реализовал свои вещи с помощью двунаправленных указателей. Когда мы добрались до бинарных деревьев, эти указатели перестали быть полезными. Правильное использование рекурсии заменяет необходимость перехода по ссылке вверх по дереву.