插入线程二进制导致 O(n) 时间复杂度？
Insertion in Threaded Binary leads leads to O(n) time complexity?
线程二叉树是有效的，因为它不需要任何递归或堆栈来遍历。我怀疑它使每次插入都需要 O(n) （其中 n 是树中的节点数），因为对于我们插入的每个节点，它都必须再次线程化，不是吗？ ？如果我是对的，那么线程二叉树实际上是无效的，不是吗？
正如 Wikipedia article 所说：
"A binary tree is threaded by making all right child pointers that
would normally be null point to the inorder successor of the node (if
it exists), and all left child pointers that would normally be null
point to the inorder predecessor of the node."
这里的关键是"that would normally be null."
通常，您要么包括线程链接的附加字段，要么使用位标志来确定左右节点是子节点还是有序 successor/predecessor。
因为内部节点指针仍然是传统的left/right二叉树节点引用，您可以使用标准递归搜索在O(log n)时间内找到插入点。
线程二叉树是有效的，因为它不需要任何递归或堆栈来遍历。我怀疑它使每次插入都需要 O(n) （其中 n 是树中的节点数），因为对于我们插入的每个节点，它都必须再次线程化，不是吗？ ？如果我是对的，那么线程二叉树实际上是无效的，不是吗？
正如 Wikipedia article 所说：
"A binary tree is threaded by making all right child pointers that would normally be null point to the inorder successor of the node (if it exists), and all left child pointers that would normally be null point to the inorder predecessor of the node."
这里的关键是"that would normally be null."
通常，您要么包括线程链接的附加字段，要么使用位标志来确定左右节点是子节点还是有序 successor/predecessor。
因为内部节点指针仍然是传统的left/right二叉树节点引用，您可以使用标准递归搜索在O(log n)时间内找到插入点。