时间戳

首页 > 解决方案 > 使用父节点创建二叉搜索树节点

c - 使用父节点创建二叉搜索树节点

问题描述

我有一个 BST 定义如下：

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

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

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

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

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

更新：有人要求查看我的删除代码。这是未经测试的，对我来说很难写（我是 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;
}

标签： cbinary-search-tree

解决方案

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

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

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

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

这真的很值得，特别是如果您不需要更改树：

  • 从只知道其地址的树中删除一个 Trnode 或
  • 当只知道现有节点的地址时，在现有节点之前或之后插入一个新节点。

推荐阅读