Pro*_*mer 6 algorithm binary-tree asymptotic-complexity binary-search-tree data-structures
关于螺纹二进制搜索树的解释(如果你知道它们,请跳过它):
我们知道在具有n个节点的二叉搜索树中,有n + 1个左右指针包含null.为了使用包含null的内存,我们按如下方式更改二叉树 -
对于树中的每个节点z:
如果left [z] = NULL,我们在left [z]中输入tree-predecessor(z)的值(即指向包含前任键的节点的指针),
如果right [z] = NULL,我们在右[z]中输入tree-successor(z)的值(同样,这是指向包含后继键的节点的指针).
像这样的树称为线程二进制搜索树,新链接称为线程.
我的问题是: 螺纹二进制搜索树的主要优点是什么(与"常规"二叉搜索树相比).在网上快速搜索告诉我,迭代地实现有序遍历有助于,而不是递归地实现.
这是唯一的区别吗？还有其他方法可以使用线程吗？
这是如此有意义的优势吗？如果是这样,为什么？递归遍历也花费O(n)时间,所以..
非常感谢你.
非递归有序扫描是一个巨大的优势.想象一下有人要求你找到值"5"和它后面的四个值.使用递归很困难.但是如果你有一个线程树,那么很简单:按递归顺序搜索找到值"5",然后按照线程链接获取接下来的四个值.
同样,如果您想要特定值之前的四个值,该怎么办？使用递归遍历很难,但如果找到项目然后向后走螺纹链接则很简单.