使用 Parent 节点创建二叉搜索树节点

Question

我有一个 BST 定义如下：

typedef struct trnode {
    Item item;
    struct trnode *left;
    struct trnode *right;
} Trnode;

typedef struct tree {
    Trnode *root;
    size_t size;
} Tree;

我经常遇到的问题是我想知道特定树节点的 parent 是什么。定义包含 parent 的树节点是否很常见，例如：

typedef struct trnode {
    Item item;
    struct trnode *parent;
    struct trnode *left;
    struct trnode *right;
} Trnode;

或者包括 parent 不应该做的事情，如果是这样：为什么不呢？

更新：有人要求查看我的删除代码。这是未经测试的，对我来说很难写（我是 C 的初学者，也只是学习 BST 数据结构）。无论如何，这里是：

Node * SeekInsertionParent(const Node *root, const Node *pnode)
{
    // cmp returns -1 (less than), +1 (greater than), or 0 (equal)
    int cmp = CmpNodes(pnode, root);
    if (cmp == 0) return NULL; // ignore this for now
    Node *child = (cmp < 0)? root->left : root->right;
    if (child == NULL)
        return root;
    else
        SeekInsertionParent(child, pnode);
}
Bool DeleteItem(Tree *ptree, const Item *pi)
{
    Node *parent;
    Node *node = SeekItem(pi, ptree);
    if (node == NULL)
        return false;

    // (1) if no children, then it's a leaf, just delete it
    if (!node->left && !node->right) {
        free(node);
        return true;
    }

    // (2) if it has one child, link that child to the parent then free the node
    if (!node->left || !node->right) {
        Node *descendant = (node->left)? node->left : node->right;
        descendant->parent = parent;
        if (parent->left == node)
            parent->left = descendant;
        else
            parent->right = descendant;
        free(node);
    }

    // (3) if it has two children, then:
    //     (a) attach the child same-side child to the parent node;
    //     (b) using the root of the attachment, find the place to insert the other-side child
    else {
        Node *insert_at, *other_side;
        if (parent->left == node) {
            node->left->parent = parent;
            parent->left = node->left;
            other_side = node->right;
        } else {
            node->right->parent = parent;
            parent->right = node->right;
            other_side = node->left;
        }

        free(node);
        insert_at = SeekInsertionParent(parent, other_node);

        if (insert_at->left == NULL) {
            insert_at->left=node;
            node->parent=insert_at;
        } else {
            insert_at->right=node;
            node->parent=insert_at;
        }
    }
    return true;
}

Answer 1

通过添加父级，您将添加 O(n) 内存，这不是您想要做的，因为大多数时候您的算法将运行在 O(logN) 中。

如果你真的想实现它，你可以简单地找到的模型并复制它来与parent一起构建BST。

请注意，您可以从 XOR Linkedlist 中获得灵感来解决内存过剩问题：

Trnode(current) = Trnode(parent)^Trnode(current->left ^ current->left)
Trnode(current->left) = Trnode(current)^Trnode(current->left->left^current->left->right)

这真的很值得，特别是如果你不需要改变树的话：

to delete a Trnode from the tree knowing only its address or

to insert a new node before or after an existing node when knowing only the address of the existing node.

Answer 2

您可能想阅读 this to understand how deletion is done without using parent pointer in node representation. In CLRS，它已给出

We can represent such a binary search tree by a linked data structure in which each node is an object. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL

他们使用 parent 指针，因为它有助于实现 delete、find-next-larger、find-next-smaller 等过程。在您的代码中使用它不是问题但是，它会花费 O(n) 额外的内存 space。请记住，如果您不在节点表示中使用 parent 指针，那么您需要实现单独的函数，该函数将 tree_node 和 tree_node 的父级 returns 作为参数，当您需要需要某些节点的父节点的过程时。

Answer 3

正如承诺的那样，简化版本，使用指针到指针。

要点是：你不需要维护父指针，因为它总是可以计算的。我创建了两个辅助函数来获取 指向指向给定节点（或值）的指针 的指针。可以在插入函数中使用相同的辅助函数。

#if 0
#include <stdlib.h>
#include <stdbool.h>
#define Bool bool
#else
typedef enum bool{ false, true} Bool;
void free(void*);
#define NULL (void*) 0
#endif

typedef struct node {
    int item;
    struct node *left;
    struct node *right;
} Node;


        // Helper function to find the pointer that points to the node containing item
static Node **node_seek_parent_pp_value(Node **pp, int item)
{
    // cmp returns -1 (less than), +1 (greater than), or 0 (equal)
    while (*pp) {
        int cmp;
        cmp = (*pp)->item == item ? 0 : (*pp)->item < item ? 1 : -1;
        if (cmp == 0) break; // Found!
        pp = (cmp < 0)? &(*pp)->left : &(*pp)->right;
        }

   return pp;
}

        // Same helper function, but with a pointer to item argument
static Node **node_seek_parent_pp_ptr(Node **pp, Node *pnode)
{
if (!pnode) return NULL;
return node_seek_parent_pp_value(pp, pnode->item);
}

Bool DeleteItem(Node **pp, int item)
{
    Node *del;

    pp = node_seek_parent_pp_value(pp, item);
    if (!pp || !*pp) return false; // Not found

    // (1) if fewer than two children
    if (!(*pp)->left || !(*pp)->right) {
        del = *pp;
        *pp = del->left ? del->left : del->right;
    }

    // (2) if it has two children, then:
    //     (a) detach one child subtree
    //     (b) insert it onto the other child
    //     (c) put this other child in place of the node to be deleted.
    else {
        Node **target, *orphan;
        del = *pp;
        orphan = del->right;
        target = node_seek_parent_pp_ptr(&del->left, orphan);
        if (!target) { // should not happen ...
            return false;
            }
        *target = orphan;
        *pp = del->left;
        }

    free(del);
    return true;
}

Bool InsertNode(Node **pp, Node * this)
{
pp = node_seek_parent_pp_ptr(pp, this);
if (!pp || *pp) return false; // this is NULL, or already existing
*pp = this; // insert
return true; // Success!
}

使用 Parent 节点创建二叉搜索树节点

Creating a Binary Search Tree node with Parent node

c

binary-search-tree