Stack Overflow
Stack Overflow

Questions tagged [multiway-tree]

A multiway tree is a tree where each node can have a variable number of children.

A tree data structure is a structure consisting of nodes with some number of children. Many trees a binary trees (each node has 0, 1, or 2 children), though trees with multiple children exist as well. This tag is appropriate for questions specifically about multiway trees.

52 questions
24
votes
1 answer

What is the left-child, right-sibling representation of a tree? Why would you use it?

Many data structures store multi-way trees as binary trees using a representation called the "left-child, right-sibling" representation. What does this mean? Why would you use it?
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
13
votes
1 answer

Drawing & Rendering Multiway Tree in Python

Does somebody know how do I plot a multiway-tree in a aesthetically plausible way? info: more or less 100 items each level have approximately the same number of items 10 levels each node have between 0(leaf) and 6 childs each node specify it's…
BrainStorm
  • 2,036
  • 1
  • 16
  • 23
12
votes
8 answers

O(1) algorithm to determine if node is descendant of another node in a multiway tree?

Imagine the following tree: A / \ B C / \ \ D E F I'm looking for a way to query if for example F is a descendant of A (note: F doesn't need to be a direct descendant of A), which, in this particular case would be true. Only a…
Philip Kamenarsky
  • 2,757
  • 2
  • 24
  • 30
11
votes
4 answers

Rank Tree in C++

We need ADT having search and rank features. That is, in addition to the interface of STL map, a function 'int get_rank(key)' is required. Standard implementation of such function requires supporting and updating an extra integer field in every node…
Slava
  • 827
  • 5
  • 13
11
votes
6 answers

How to implement a Non-Binary tree

I am having trouble implementing a non-binary tree, where the root node can have an arbitrary amount of child nodes. Basically, I would like some ideas on how where to go with this, since I do have some code written, yet I'm stuck at this point on…
Karim O.
  • 1,325
  • 6
  • 22
  • 36
9
votes
4 answers

Algorithm for Tree Traversal

Update: I found more of an example of what I'm trying to pull off: Managing Hierarchical Data in MySQL. I want to do that but in JavaScript because I am building an app that takes in comments that are in a hierarchical structure, to be more…
HuXu7
  • 317
  • 3
  • 13
8
votes
2 answers

Fold / Recursion over Multiway Tree in f#

I am trying to adapt Brian's Fold for Binary Trees (http://lorgonblog.wordpress.com/2008/04/06/catamorphisms-part-two/) to apply for Multiway trees. Summarizing from Brian's Blog: Data structure: type Tree<'a> = | Node of (*data*)'a *…
dusio
  • 480
  • 5
  • 18
8
votes
6 answers

Minimum damaging costs in graph

We are given a graph G(V,E) with N nodes (Numbered from 0 to N-1) and exactly (N-1) two-way Edges. Each edge in a graph has a positive cost C(u,v)(Edge weight). The entire graph is such that there is a unique path between any pair of Nodes. We are…
Ritesh Kumar Gupta
  • 5,055
  • 7
  • 45
  • 71
7
votes
5 answers

splitting a node in b+ tree

I'm trying to figure out what exactly happens when there is a node overflow. info: in my b+ tree there are 4 pointers per block and 3 data sections . problem: I understood that when there is an overflow we split into 2 nodes in my case each with…
farchy
  • 71
  • 1
  • 2
6
votes
3 answers

Progressively store the path from root node to node of multiway tree during insertion so that the storage operation does not have a complexity of O(n)

I would like to ask if someone knows a performant way to store the path from the root node to a new node of a multiway tree during the insertion of the new node. E.g., if I have the following tree: For each node, I currently store an array of the…
tonix
  • 6,671
  • 13
  • 75
  • 136
6
votes
7 answers

How to load/save C++ class instance (using STL containers) to disk

I have a C++ class representing a hierarchically organised data tree which is very large (~Gb, basically as large as I can get away with in memory). It uses an STL list to store information at each node plus iterators to other nodes. Each node has…
ati
  • 307
  • 3
  • 10
6
votes
2 answers

Data structures: Which should I use for these conditions?

This shouldn't be a difficult question, but I'd just like someone to bounce it off of before I continue. I simply need to decide what data structure to use based on these expected activities: Will need to frequently iterate through in sorted order…
Daddy Warbox
  • 4,500
  • 9
  • 41
  • 56
5
votes
1 answer

Multiway tree construction from a node string

There is a wonderful problem set called Ninety-Nine Prolog Problems. Problem P70 is the one referred to in the title. And here is a great Prolog solution of this problem which takes only 5 lines. However, my understanding of Prolog is limited. How…
John
  • 95
  • 5
5
votes
1 answer

"Simple" Trie Implementation

I need to implement a Trie (in Java) for a college project. The Trie should be able to add and remove Strings (for phase 1). I have spent several hours each day (for the last few days) trying to figure out how to do this and FAILED miserably each…
user3553706
  • 51
  • 3
5
votes
2 answers

Max Value of a Multiway Tree in OCaml

I'm an IT Student and kind of a newbie to OCaml Recently, studying for an exam I found this exercise. Given: type 'a tree = Tree of 'a * 'a tree list Define a function mtree : 'a tree ->'a, that returns the greatest value of all the nodes in a…
Trigork
  • 177
  • 1
  • 16
1
2 3 4