Wednesday, March 18, 2009

We'd like to return to the binary tree algorithms and spell what you cannot do with generics in C#. Well, you can do many things, however with generalization penalty.

Consider a binary tree node: `Node(Parent, Left, Right)`. RB, AVL, and others algorithms attach some private information to this node to perform balancing.

You can express this idea methematically (and in C++), you cannot implement it efficiently in C#.

More focused example. Consider RB tree: `Node(Parent, Left, Right, Color)`. There are a number of ways you may implement the internal structure of the tree. Algorithms themselves stay the same.

Straightforward implementation:

```class Node {   Node Parent;   Node Left;   Node Right;   bool Color; }```

This implementation allocates nodes in the heap and each node refers to other nodes.

Node navigator implementation:

```class Node {   Node Left;   Node Right;   bool Color; } struct NodeNavigator {   Node[] nodes;   int index; }```

Node does not refer to the parent. This reduces the memory consumption and simplifies object graph, which is good for GC. Tree is walked using a node navigator, which stores ancestors of the node.

Node as a structure:

```struct Node {   int Parent;   int Left;   int Right;   bool Color; // This might be integrated as highest bit of parent. } ```

Tree is stored as an array of nodes. This is compact and GC efficient implementation.

Node as a structure, and with node navigator:

```struct Node {   int Left;   int Right;   bool Color; // This might be integrated as highest bit of left. } struct NodeNavigator {   Tree tree;   int[] nodes;   int index; }```

Tree is stored as an array of nodes, and a navigator is used to walk it. This is the most compact implementation.

Each implementation has its virtues. The common between implementations is that they share the same balancing and navigation algorithms. Storage differences prevent a single C# implementation. To the contrast, C++ allows to define a concept "tree" and to define specializations of this concept, allowing a unified algorithms; all this is done without performance penalty.

P.S. java in this regard, is almost alternativeless...

Wednesday, March 18, 2009 6:53:05 AM UTC      Comments [0] -
Incremental Parser | Tips and tricks
All comments require the approval of the site owner before being displayed.
 Name E-mail Home page Remember Me Comment (Some html is allowed: `a@href@title, b, blockquote@cite, em, i, strike, strong, sub, super, u`) where the @ means "attribute." For example, you can use or
. Enter the code shown (prevents robots): Live Comment Preview
Archive
 < May 2022 >
SunMonTueWedThuFriSat
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234
Categories
 .NET Angular AngularJS Announce ASP.NET Azure BizTalk Server C++ Incremental Parser Java javascript JSF and Facelets kendoui ML.NET SCCBridge SQL Server puzzle Thinking aloud Tips and tricks Window Search xslt
Blogroll
Statistics
Total Posts: 381
This Year: 2
This Month: 0
This Week: 0