调用函数后指向 B 树根节点的指针开始指向子节点（应该继续指向根节点）

Question

下面的B-Tree代码是取自CLRS第3版->高级数据结构->第18章的算法代码表示。

我已经为 btree_insert、btree_split_child、btree_insert_nonfull 函数编写了代码。

来自 CLRS 的转向：代码遵循 LEFT-CHILD，RIGHT-SIBLING 表示，具有无限分支的有根树。

Btree 的最小度为 3。

/* Representing rooted trees with unbounded branching :-
 *
 * LEFT-CHILD, RIGHT-SIBLING representation : Instead of having a pointer to each of its children,
 * however, each node x has only two pointers:
 * x.left-child points to the leftmost child of node x, and
 * x.right-sibling points to the sibling of x immediately to its right.
 *
 * If x has no children, then x.left-child = NIL, and if node x is the rightmost child of its parent,
 * then x.right-sibling = NIL.
 *
 */

/* assume t = 3 situation 
 * Therefore, lowerbound on #keys = 2 and upperbound = 2t - 1 keys, i.e 5 keys */

#include <stdio.h>
#include <stdlib.h>

#define DEGREE 3

struct s_btree_node
{
  int leaf;
  int total_keys;

  int keys[2 * DEGREE - 1];

  struct s_btree_node * left_child;
  struct s_btree_node * right_sibling;
};

/* helper functions for btree structure */

/* pointer to the root node of the BTree structure */
static struct s_btree_node * proot = NULL;

/* allocate new node on the heap */
struct s_btree_node * new_node(void);

void btree_split_child (struct s_btree_node * proot, int i);

void btree_insert_nonfull (struct s_btree_node * proot, int key);

void btree_insert_node(struct s_btree_node * pnode, int key);

int main(int argc, char * argv[])
{
  proot = new_node();

  btree_insert_node(proot, 8);
  btree_insert_node(proot, 1);
  btree_insert_node(proot, 11);
  btree_insert_node(proot, 5);
  btree_insert_node(proot, 13);
  btree_insert_node(proot, 7);
  btree_insert_node(proot, 28);
  btree_insert_node(proot, 2);
}

struct s_btree_node * new_node()
{
  struct s_btree_node * pnode = (struct s_btree_node *)malloc(sizeof(struct s_btree_node));

  pnode->leaf = 1;
  pnode->total_keys = 0;
  pnode->left_child = NULL;

  return pnode;
}

void btree_split_child (struct s_btree_node * pnode, int i)
{
  /* pnew_split_node is z in CORMEN */
  struct s_btree_node * pnew_split_node = new_node();


  /* CORMEN: line 2 */
  /* Traverse tree to get the correct right-sibling. Conceptually y is x's i-th child */
  int j = 0;
  struct s_btree_node * pstud = pnode->left_child;
  /* Get x.c_suffix_i */
  while (pstud != NULL && j < i) {
    pstud = pstud->right_sibling;
    j++;
  }
  /* poriginal_split_node is y in CORMEN */
  struct s_btree_node * poriginal_split_node = pstud;


  /* CORMEN: line 3 */
  pnew_split_node->leaf = poriginal_split_node->leaf;
  /* CORMEN: line 4 */
  pnew_split_node->total_keys = DEGREE - 1;

  /* CORMEN: line 5 */
  j = 0;
  while (j <= DEGREE - 2) {
    pnew_split_node->keys[j] = poriginal_split_node->keys[j + DEGREE];
    j++;
  }


  /* CORMEN: line 7 */
  if (poriginal_split_node->leaf == 0) {
    int k = 1;
    /* find starting child node */
    struct s_btree_node * poriginal_split_node_child = poriginal_split_node->left_child;
    while (k < k + DEGREE) {
      poriginal_split_node_child = poriginal_split_node_child->right_sibling;
      k++;
    }

    /* Assign rest of the child chain of poriginal_spilt_node to pnew_split_node */
    pnew_split_node->left_child = poriginal_split_node_child->right_sibling;
    /* Make right_sibling of poriginal_split_node_child point to NULL */
    poriginal_split_node_child->right_sibling = NULL;
  }

  /* CORMEN: line 10 */
  /* Remove redundant keys of poriginal_split_node */
  poriginal_split_node->total_keys = DEGREE - 1;
  int l = 2 * DEGREE - 1;
  while (l > poriginal_split_node->total_keys + 1) { /* Keep key 'keys[DEGREE - 1]' till it is promoted to parent */
    poriginal_split_node->keys[l - 1] = 0;
    l--;
  }


  /* CORMEN: line 11-13 */
  pnew_split_node->right_sibling = poriginal_split_node->right_sibling;
  poriginal_split_node->right_sibling = pnew_split_node;

  /* CORMEN: line 14-16 */
  int k = pnode->total_keys;
 while (k > i) {
    pnode->keys[k] = pnode->keys[k - 1];
    k--;
  }
  pnode->keys[i] = poriginal_split_node->keys[DEGREE - 1];

  /* After key 'key[DEGREE - 1]' from poriginal_split_node has been promoted to parent,
   * remove it from poriginal_split_node */
  poriginal_split_node->keys[DEGREE - 1] = 0;

  /* CORMEN: line 17 */
  pnode->total_keys = pnode->total_keys + 1;
}

void btree_insert_nonfull (struct s_btree_node * pnode, int key)
{
  int i = pnode->total_keys;

  if (pnode->leaf == 1) {
    while (i >= 1 && key < pnode->keys[i - 1]) {
      pnode->keys[i] = pnode->keys[i - 1];
      i = i - 1;
    }
    pnode->keys[i] = key;
    pnode->total_keys = pnode->total_keys + 1;
  } else {
    while (i >= 1 && key < pnode->keys[i - 1]) {
      i = i - 1;
    }

    i = i + 1;

    /* traverse to correct child node */
    int j = i;
    struct s_btree_node * pchild_node = pnode->left_child;
    while (j > 1) {
      pchild_node = pchild_node->right_sibling;
      j--;
    }

    if (pchild_node->total_keys == 2 * DEGREE - 1) {
      btree_split_child(pnode, i);
      if (key > pnode->keys[i - 1]) {
        i = i + 1;
      }
    }

    btree_insert_nonfull(pchild_node, key);
  }
}

void btree_insert_node (struct s_btree_node * proot, int key)
{
  struct s_btree_node * pnode = proot;

  if (pnode->total_keys == 2 * DEGREE - 1) {
    struct s_btree_node * psplit_node = new_node();
    proot =  psplit_node;
    psplit_node->leaf = 0;
    psplit_node->total_keys = 0;
    psplit_node->left_child = pnode;

    btree_split_child(psplit_node, 0);
    btree_insert_nonfull(psplit_node, key);
  } else {
    btree_insert_nonfull(pnode, key);
  }
}

调试会话：-

Reading symbols from btree...done.
(gdb) b 74
Breakpoint 1 at 0x4005a5: file BTree.c, line 74.
(gdb) b 247
Breakpoint 2 at 0x400a31: file BTree.c, line 247.
(gdb) b 75
Breakpoint 3 at 0x4005b9: file BTree.c, line 75.
(gdb) run

Breakpoint 1, main (argc=1, argv=0x7fffffffdee8) at BTree.c:74
74        btree_insert_node(proot, 7);
(gdb) p * proot
 = {leaf = 1, total_keys = 5, keys = {1, 5, 8, 11, 13}, left_child = 0x0, right_sibling = 0x0}
(gdb) n

Breakpoint 2, btree_insert_node (proot=0x602050, key=7) at BTree.c:247
247             btree_insert_nonfull(psplit_node, key);
(gdb) p * proot
 = {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}
(gdb) p * proot->left_child
 = {leaf = 1, total_keys = 2, keys = {1, 5, 0, 0, 0}, left_child = 0x0, right_sibling = 0x602090}
(gdb) p * proot->left_child->right_sibling
 = {leaf = 1, total_keys = 2, keys = {11, 13, 0, 0, 0}, left_child = 0x0, right_sibling = 0x0}
(gdb) n
251     }
(gdb) p * proot
 = {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}
(gdb) n

Breakpoint 3, main (argc=1, argv=0x7fffffffdee8) at BTree.c:75
75        btree_insert_node(proot, 28);
(gdb) p * proot
 = {leaf = 1, total_keys = 3, keys = {1, 5, 7, 0, 0}, left_child = 0x0, right_sibling = 0x602090}
(gdb)

在执行 btree_split_child 到 main 函数后从 btree_insert_node returns 调用时，就在行 btree_insert_node(proot, 28) 执行之前，我打印 * proot, 给出了意想不到的结果。

在调试会话结束时，proot 应该是 {leaf = 0, total_keys = 1, keys = {8, 0, 0, 0, 0}, left_child = 0x602010, right_sibling = 0x0}。而是 {leaf = 1, total_keys = 3, keys = {1, 5, 7, 0, 0}, left_child = 0x0, right_sibling = 0x602090}.

我是C语言的新手。对改进我的代码的任何其他建议表示赞赏。

Answer 1

在 btree_insert_node 中，s_btree_node* proot 是指向结构的指针，而不是指向指针的指针。因此，当您在 proot = psplit_node 中修改它时，只会修改本地副本。

您可以 return 一个新的根。这应该有效：

...
struct s_btree_node * btree_insert_node(struct s_btree_node * pnode, int key);

int main(int argc, char * argv[])
{
    proot = new_node();

    proot = btree_insert_node(proot, 8);
    proot = btree_insert_node(proot, 1);
    proot = btree_insert_node(proot, 11);
    proot = btree_insert_node(proot, 5);
    proot = btree_insert_node(proot, 13);
    proot = btree_insert_node(proot, 7);
    proot = btree_insert_node(proot, 28);
    proot = btree_insert_node(proot, 2);
}

...

struct s_btree_node * btree_insert_node(struct s_btree_node * proot, int key)
{
    struct s_btree_node * pnode = proot;

    if (pnode->total_keys == 2 * DEGREE - 1) {
        struct s_btree_node * psplit_node = new_node();
        proot = psplit_node;
        psplit_node->leaf = 0;
        psplit_node->total_keys = 0;
        psplit_node->left_child = pnode;

        btree_split_child(psplit_node, 0);
        btree_insert_nonfull(psplit_node, key);
        return proot; //return a new tree-root after insertion
    }
    else {
        btree_insert_nonfull(pnode, key);
        return proot; //tree-root was not changed - return it
    }
}

Answer 2

在 C 中，当您将任何内容传递给函数时，函数会创建它自己的参数副本，无论是 int、指针等。

在函数 btree_insert_node 中，您有一个名为 *proot 的参数，您将向其传递全局变量 proot。假设你的全局 proot 变量的地址是 gpa，它的值是 gpv。当您在函数 btree_insert_node 中传递此全局变量时，它的局部变量 proot（假设地址为 lpa）获取 gpv 的值。然后当你做 proot = psplit_node; 这个本地 proot 变量的值被改变，而不是全局的。假设 psplit_node 的值是 psnv，那么在操作之后：

本地根地址：lpa，本地根值：psnv

全局根地址：gpa，全局根值：gpv

global proot 的值保持不变，这不是你的本意。

解决这个问题很简单，从函数 btree_insert_node 中删除参数 proot，因为您已经有了全局 proot

这应该有效：

int main(int argc, char * argv[])
{
  proot = new_node();

  struct s_btree_node * a;

  btree_insert_node(8);
  btree_insert_node(1);
  btree_insert_node(11);
  btree_insert_node(5);
  btree_insert_node(13);
  btree_insert_node(7);
  btree_insert_node(28);
  btree_insert_node(2);
}
...
void btree_insert_node (int key)
{
  struct s_btree_node * pnode = proot;

  if (pnode->total_keys == 2 * DEGREE - 1) {
    struct s_btree_node * psplit_node = new_node();
    proot =  psplit_node;
    psplit_node->leaf = 0;
    psplit_node->total_keys = 0;
    psplit_node->left_child = pnode;

    btree_split_child(psplit_node, 0);
    btree_insert_nonfull(psplit_node, key);
  } else {
    btree_insert_nonfull(pnode, key);
  }
}

调用函数后指向 B 树根节点的指针开始指向子节点（应该继续指向根节点）

Pointer to root node of B-tree after call to a function begins pointing to a child ( should continue pointing to root instead )

c

algorithm

pointers

b-tree

data-structures