双向二叉搜索树？

Question

我已经尝试实现了BST。到目前为止，它只根据BST属性(Left- now，Right-Bigger)添加关键字。尽管我以不同的方式实现了它。

我认为BST应该是这样的

Single Direction BST

我是如何实现BST的

Bi-Directional 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

您还没有描述如何使用父指针获得任何东西。关心回溯到父节点的算法将通过向上爬行调用堆栈来做到这一点。

我曾经经历过--在我的数据结构类中，我用双向指针实现了我的东西。当我们到达二叉树时，这些指针就不再有用了。正确使用递归取代了在树上沿着链接返回的需要。