The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
6 views

Dynamic Approach For LCA

I reading a LCA Tutorial Where it defines P[1,N][1,logN] where P[i][j] is the 2j-th ancestor of i Why it is using logN and why 2j ancestor is used ? I did not understand it's intuition ?
-1
votes
0answers
27 views

get rules of Weka J48 Decision tree [closed]

I want to display a Weka classification tree to the end-user that I have generated using weka.jar in Java. But not the default tree in grey window titled as "Tree Visualizer" which is obtained via ...
1
vote
1answer
94 views

Why are heuristics a disadvantage for decidable problems?

I'm reading Introduction to Artificial Intelligence by Ertel. This line has me stumped from the textbook (page 102): For decidable problems such as the 8-puzzle this means that the whole search ...
5
votes
4answers
197 views

Most efficient way to generate all descendents of all nodes in a tree

I'm looking for the most efficient algorithm to take a tree (stored as either a list of edges; OR as a list of mappings from parent node to a list of child nodes); and produce, for EVERY node, a list ...
1
vote
2answers
88 views

How to randomly get or find a sub-tree (include root node) from a given tree that contains n leaf-nodes

I have a non-binary tree. I want to randomly find a "sub-trees" that are connected from root to leaf which must have at least n leaf-nodes (leaf-nodes of sub-tree must be leaf-nodes of given tree). ...
1
vote
1answer
104 views

Where to put data for tree structure which every node requires?

I have a quad-tree structure where each node has some of its own data, but there is also data which applies to the tree as a whole. I'll explain my current solution and I would appreciate feedback on ...
0
votes
0answers
77 views

Algorithm for sport tournament bracket tree

I would like to develop a library that: receive n players in input response with the tournaments brackets in output. I would ask you what kind of algorithm I have to use to choose the correct tree ...
1
vote
0answers
79 views

Walk Tree vs Zhang and Sasha Algorithms

I need some help understanding how two tree comparing algorithms differ. I am working with Microsoft's XmlDiffPatch (http://msdn.microsoft.com/en-us/library/aa302294.aspx) which compares two xmls. The ...
0
votes
1answer
150 views

how to traverse towards child node from parent node in n-ary tree? [closed]

In an n-ary tree... Given a reference to some child node And a reference to a distant parent of the referenced child node Is there a method that a parent node can use to figure out which of its ...
2
votes
1answer
124 views

Data structures and algorithms for a directed rooted tree with inherited properties?

I need to represent a directed rooted tree in memory. The caveat is, that nodes have properties. And those properties are inherited (but not 100%) by the child nodes, recursively. What would be a ...
3
votes
1answer
87 views

Which data structures and algorithms should I consider for a directed rooted tree that has high churn?

I need to represent a directed rooted tree in memory. What would be a good data structure and algorithms for performing main actions, given the particulars listed below? Size: ~40,000 nodes. But ...
3
votes
3answers
395 views

How exactly is an Abstract Syntax Tree created?

I think I understand the goal of an AST, and I've built a couple of tree structures before, but never an AST. I'm mostly confused because the nodes are text and not number, so I can't think of a nice ...
1
vote
1answer
166 views

Performing a Depth First Search iteratively using async/parallel processing?

Here is a method that does a DFS search and returns a list of all items given a top level item id. How could I modify this to take advantage of parallel processing? Currently, the call to get the sub ...
1
vote
1answer
64 views

Find common ancestor

Given X number of leaves (the ringed leaves in the picture) in an unbalanced tree with depth aroun 100-1000 and total number of nodes around 15 000 000. I'm looking for the first common ancestor for ...
1
vote
0answers
127 views

Menu building pattern

I'm having troubles getting my head around the active-state handling of a menu when the menu isn't used for routing. I come from Drupal where the menu system handles the routing as well. so setting ...
1
vote
3answers
86 views

Handling leaves in tree-based menus

Tl;Dr Given a language with no polymorphism how to you elegantly modify the behavior of a leaf in a tree data structure. Context I'm programming an application in C for a microcontroller and I'm ...
3
votes
3answers
176 views

Quadtree with duplicates

I'm implementing a quadtree. For those who don't know this data strucutre, I am including the following small description: A Quadtree is a data structure and is in the Euclidean plane what an ...
1
vote
0answers
89 views

Most efficient way to rebuild a tree structure from data

Have a question on recursively populating JsTree using the .NET wrapper available via NuGet. Any help would be greatly appreciated. the .NET class JsTree3Node has a property named Children which ...
0
votes
2answers
477 views

Exercise 3.6: Skiena Algorithm Design Manual

I am preparing for interview and try to solve the exercise problems of the book. 3-6. [5] Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and ...
1
vote
2answers
631 views

Tree View Children condition indicator on topmost un-expanded parent

I am using a tree view in c# and i am creating custom icons for the nodes. Let say this is my hierarchy with a node that satisfies a certain condition: Root1 |_Ax |_Bx1 |_Bx2 |_Cx1 ...
2
votes
1answer
125 views

Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
0
votes
1answer
455 views

What happens to equal elements when inserting into a binary search tree?

Most BST examples show a sample of a BST with unique values; mainly to demonstrate the order of values. e.g. values in the left subtree are smaller than the root, and values in the right subtree are ...
2
votes
2answers
127 views

Segregating interfaces/concerns to a tree

When working with a single object there are a number of ways to segregate interfaces to it. Breaking it into smaller components that can be treated independently. Breaking it into simpler ...
0
votes
4answers
249 views

What do you call a tree that grows in both directions? [closed]

What would be the technical term for a tree that grows in both the directions, starting from the root in the middle? The central idea being that new elements can be added to the tree (Now, I am not ...
1
vote
1answer
189 views

About AST construction in LL1 non recursive parser

I have implemented a LL1 parser in a non recursive approach with a explicit stack. The following algorithm is from the Dragon Book: set zp to point to the first symbol of w; set X to the top stack ...
0
votes
0answers
80 views

Looking for a Treemap tiling algorithm

I'm looking for an algorithm to convert a tree of data into a 2 dimensional treemap view. http://en.wikipedia.org/wiki/Treemapping I can do all the coloring in and drawing myself, but if there was ...
0
votes
1answer
71 views

What is the difference between a Splay Tree and an Optimal Binary Search Tree?

Both these trees try to keep the most frequently accessed element at the top. Is there any difference between these two trees?
1
vote
2answers
1k views

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
6
votes
4answers
5k views

How do I traverse a tree without using recursion?

I have a very large in memory node tree and need to traverse the tree. Passing the returned values of each child node to their parent node. This has to be done until all the nodes have their data ...
0
votes
1answer
54 views

Verify 0 or 2+ sub sections in a section

There is a rule in writing: When you break a section into subsections, typically it should have more than one subsection. This goes back to the old high school composition rules: if you have an A. ...
4
votes
3answers
509 views

Is a tree with nodes that have reference to parent still a tree?

If we make reference to the parent for each node in a tree, do we still have a tree (by definition) anymore? Wikipedia definition is: In computer science, a tree is a widely used abstract data ...
4
votes
3answers
426 views

Optimal “if-else” tree algorithm to minimize duplicate code

I'm having trouble formulating this problem as an algorithm: I have a set of conditionals (combined with &&) and operations, for example: if (A && B) execute C else if (D ...
0
votes
1answer
93 views

Tree position terminology/naming [closed]

This is a naming things question. I am processing trees (XML documents), and there are often special rules applied to nodes based on structure. It's been very difficult coming up with concise naming ...
3
votes
2answers
134 views

Reconstructing a tree from depth information

I have a data structure that describes a tree. Nodes are ordered, with "depth" information, and knowing the order and the depth the tree can be reconstructed. I'm not entirely sure how to describe it ...
0
votes
2answers
100 views

By the definition of a Tree(ADT), is it “wrong” for a node to add a sibling?

The title pretty much says it all. I'm just having a little computer science exercise and am building a Tree. I want a node to be able to add a sibling which requires one to first get a reference to ...
1
vote
1answer
116 views

Is there a name for this tree variant?

So I've created (and I'm sure someone else has come up with this before - I'm not claiming to have invented it) a data structure which consists of a binary search tree, only instead of each node ...
-1
votes
2answers
79 views

Store a tree with near next neighbours

I would to find an efficient structure (speed and volume) to store nodes and their neighbourhood. My input is build out of stings in the following format ./X/Y.log where X ∈ [0,359] and Y ...
4
votes
2answers
103 views

Placing elements in graph with a streaming/online algorthm

We have a stream of points with about 1000 points per second. For each point, we have a complex vector (hundreds of dimensions). Our goal, for each point is to link it to the 5 closest points that ...
4
votes
1answer
2k views

Homogeneous vs. heterogeneous AST representation

What are the reasons to choose a homogeneous vs. a heterogeneous AST representation for implementing a complex domain-specific programming language? Just to be very clear about what I'm asking, here ...
2
votes
3answers
1k views

How can you prove an acyclic graph has n-1 edges? [closed]

I'm not so hot on the maths for this but for what I understand... A graph g exists with v vertices and edges. g = (V,E); The spanning graph for this is an acyclic copy of this where all the vertices ...
14
votes
3answers
5k views

Implementing the Visitor Pattern for an Abstract Syntax Tree

I'm in the process of creating my own programming language, which I do for learning purposes. I already wrote the lexer and a recursive descent parser for a subset of my language (I currently support ...
2
votes
1answer
489 views

Finding subtree in a tree

I have a tree: a / \ b c / \ d f / \ g h And the pattern: x / \ y z / \ q p As output I would like to have: x: a y: b z: c q: d p: f and x: b y: f z: c q: ...
1
vote
1answer
297 views

Name for a tree where nodes hold a reference to their parent as well as their children

I am creating a tree where some nodes have a reference to their parent as well as their children. It feels like a tree version of a doubly linked list. Is there a name for this?
4
votes
1answer
112 views

Design pattern for isomorphic trees

I want to create a data structure to work with isomorphic tree. I don't search for a "algorithms" or methods to check if two or more trees are isomorphic each other. Just to create various trees with ...
1
vote
2answers
1k views

Tree vs Graphs in search

Could anyone give a clear and concise explanation for when you use graphs vs when to use trees for data structures?
4
votes
2answers
890 views

Patterns for a tree of persistent data with multiple storage options?

I have a real-world problem which I'll try to abstract into an illustrative example. So imagine I have data objects in a tree, where parent objects can access children, and children can access ...
0
votes
0answers
145 views

How to find optimal path visit every node with parallel workers complicated by dynamic edge costs?

Say you have an acyclic directed graph with weighted edges and create N workers. My goal is to calculate the optimal way those workers can traverse the entire graph in parralel. However, edge costs ...
6
votes
1answer
2k views

What is the usage of Splay Trees in the real world?

I decided to learn about balanced search trees, so I picked 2-3-4 and splay trees. What are the examples of splay trees usage in the real world? In this Cornell: ...
1
vote
2answers
671 views

Count function on tree structure (non-binary)

I am implementing a tree Data structure in c# based (largely on Dan Vanderboom's Generic implementation). I am now considering approach on handling a Count property which Dan does not implement. The ...
5
votes
2answers
377 views

Web Crawler for Learning Topics on Wikipedia [closed]

When I want to learn a vast topic on Wikipedia, I don't know where to start. For instance say I want to learn about Binary Stars, I then have to know other things linked on that pages and linked pages ...