以内存效率管理二叉树中的副本

Question

我有一个自平衡键值二叉树(类似于Tarjan的Zip树)，其中将有重复的键。为了确保O(log N)性能，我能想到的唯一办法就是在每个节点上维护三个指针；一个小于、一个大于和一个“等于”。equals指针是指向具有相同键的成员的链表的指针。

对我来说，这似乎是内存效率低下，因为我将在整个树中的每个节点上额外使用8个字节来处理不频繁的重复出现。有没有更好的方法不涉及“作弊”，比如比特敲击左指针或右指针作为标志？

Answer 1

• 当发生冲突插入时，分配新的缓冲区，复制新的数据。
• 将新的数据指针散列为一个或两个字节。你需要一个只在零输入时返回零的散列！
• 将散列值存储在你的节点中。如果没有冲突数据，此字段将为零，因此对于没有额外数据元素的所有键，您的值为O(对数KeyCount)。最坏的情况是log KeyCount加上您的散列算法在查找时产生的任何结果，这可能是一个常量，直到您的表必须调整大小。

显然，散列算法的选择在这里至关重要。无论你的目标是哪种架构，都要找一个指针值好的。对于不同的架构，您可能需要不同的哈希。

您可以通过仅使用一个字节的散列值来进一步实现这一点，该散列值将获得散列表，然后您可以使用键散列(可以是更大的整数)来查找指向其他数据的指针。当哈希表填满时，在父表中插入一个新的哈希表。我会把数学问题留给你。

关于数据局部性。因为节点数据很大，你已经没有很好的节点记录到实际的数据位置了。这种方案不会改变这一点，除非对于特定键有多个数据节点，在这种情况下，缓存未命中可能会到达节点中嵌入的变量数组的正确索引。此方案避免了在发生冲突时必须重新分配节点，并且可能不会对缓存未命中率产生严重影响。

Answer 2

当我执行二进制搜索树时，我通常使用这个设置，它跳过数组中的重复值：

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

#define SIZE 13

typedef struct Node
{
  struct Node * right;
  struct Node * left;
  int value;
}TNode;

typedef  TNode * Nodo;

void bst(int data, Nodo * p )
{
Nodo pp = *p;
  if(pp == NULL)
  {
    pp = (Nodo)malloc(sizeof(struct Node));
    pp->right = NULL;
    pp->left = NULL;
    pp->value = data;
    *p = pp;
  }
  else if(data == pp->value)
    {
      return;
    }
  else  if(data > pp->value)
    {
      bst(data, &pp->right);
    }
  else
    {
      bst(data, &pp->left);
    }

  }

void displayDesc(Nodo p)
{
  if(p != NULL)
  {

  displayDesc(p->right);
  printf("%d\n", p->value);
  displayDesc(p->left);

  }
}

void displayAsc(Nodo p)
{
  if(p != NULL)
  {

  displayAsc(p->left);
  printf("%d\n", p->value);
  displayAsc(p->right);

  }
}


int main()
{
  int arr[SIZE] = {4,1,0,7,5,88,8,9,55,42,0,5,6};

Nodo head = NULL;

for(int i = 0; i < SIZE; i++)
  {
    bst(arr[i], &head);
  }

displayAsc(head);
  exit(0);
}