开发者

How are B Tree nodes typically represented?

开发者 https://www.devze.com 2022-12-19 23:23 出处:网络
I\'ve been doing some brushing up on my B-Tree and 2-3-4 tree (B tree with order 4), and I\'m attempting to implement this in C#.My question to you is, given that a B-Tree node can contains N-1 number

I've been doing some brushing up on my B-Tree and 2-3-4 tree (B tree with order 4), and I'm attempting to implement this in C#. My question to you is, given that a B-Tree node can contains N-1 number of items and N subtrees, what is the typical representation for one of these nodes? Is it an array开发者_高级运维, series of linked-lists, or something I've not considered?


For a 2-3-4 tree, it does not really matter. For large orders, you'd use a sorted array and binary search. For variable-size keys like Strings, a trie might be a good idea.


Don't try to combine sub-trees and items. You will need 2 arrays or List<>'s.

If your order is fixed i would use 2 arrays. Otherwise, a List<ItemClass> and a List<SubTree>


Here's an interesting article on MSDN about writing a binary search tree in C#. Not exactly the same as a b-tree but you may find it useful. The author in this case uses a generic Collection base class:

public class Node<T>
{
   private T data;
   private NodeList<T> neighbors = null;
   ...
}

public class NodeList<T> : Collection<Node<T>> { ... }
0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号