CODEWITHSUNDEEP
stringdata-structurestreetrie
장예은
장예은

Reputation: 23

What kind of tree is this that has letters as nodes?

I just started learning C++ and I need to create a tree of lists (Image link below) for a project but I'm not sure if it is a custom tree or a preexisting tree.

A bit on the tree; big blue blocks represent lists, smaller blocks inside represent nodes.

I am not looking for code or anything, just an explanation of the tree or links to where I could find information on it.

Image Here

Upvotes: 2

Views: 158

Answers (4)

GAURANG VYAS
GAURANG VYAS

Reputation: 689

The data structure in the image is Trie data structure.

Trie is an efficient information retrieval data structure. Using trie, search complexities can be brought to optimal limit (key length). - (Source : GeeksForGeeks)

Trie shown in the image is made for the following strings -
Act, Actual, Actually, And, Book, Boss, Bore, Board and Boat.

Some useful links to know more -

Upvotes: 1

viraptor
viraptor

Reputation: 34145

What you're describing is an implementation of a Trie, or a prefix tree. https://en.wikipedia.org/wiki/Trie

The levels can be implemented in different ways: linked lists, bitmaps, arrays, etc. But the idea behind them is the same.

Upvotes: 0

Kattie.S
Kattie.S

Reputation: 117

This looks like a costume tree to me. Usually for projects they make their own costume tree that is a combination of data structures. for example this is a combination of lists, and linked lists.

Upvotes: 0

6502
6502

Reputation: 114481

From the picture I'd use something like

struct List;
struct Node {
    // ... node data ...
    std::shared_ptr<List> list;
};
struct List {
    // ... list data ...
    std::vector<std::shared_ptr<Node>> nodes;
};

unless the number of nodes in a list can be huge and you need to dynamically insert/remove nodes from the middle of a list.

Upvotes: 0

Related Questions