平衡的树状数据结构，调整为大小 [英] balanced tree-like data structure that resizes to prime sizes

问题描述

与此相关：堆栈溢出问题，

在那里我发现，.Net字典调整到下一个主要大小，至少是当前大小的两倍，我想知道是否有任何平衡的树状数据结构，可以调整大小到主要大小（类似于B树或二叉树）。

.Net的字典背后的树状数据结构是什么？

谢谢。

解决方案

该词典使用哈希表算法，它将数据存储在数组中，这个数组是基于素数的大小/重新大小的。 >

.NET SortedDictionary 使用红黑树结构来维护Key / Value对。由于红黑树并非存储在固定数组中，而是作为具有左/右子节点的节点上的一系列节点，因为节点被添加到树被旋转到的树中，所以没有确定任何尺寸的概念保持平衡。

Relating to this: stack overflow question,

where I found out that .Net dictionaries resize to the next prime size that is at least twice the current size, I was wondering if there is any balanced tree-like data structure that can resize to prime sizes (similar to B-Trees or Binomial trees maybe).

What is the tree-like data structure behind .Net's dictionaries?

Thanks.

解决方案

The Dictionary uses a hash table algorithm, which stores the data in an array, it is this array that is sized/re-sized based on Prime numbers.

.NET SortedDictionary uses a Red-Black tree structure to maintain the Key/Value pairs. Since the red-black tree is not stored in a fixed array, but rather as a series on nodes with left/right child nodes, there is not really a concept of sizing anything, as nodes are added to the tree the tree is rotated to maintain the balance.

这篇关于平衡的树状数据结构，调整为大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！