Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

Filter by
Sorted by
Tagged with
127 votes
5 answers
152k views

What's the difference between a binary search tree and a binary heap?

These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
Piper's user avatar
  • 1,759
107 votes
7 answers
87k views

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...
CodyBugstein's user avatar
  • 2,957
101 votes
5 answers
10k views

What are the reasons to learn different algorithms / data structures serving the same purpose?

I have been wondering about this question since I was an undergraduate student. It is a general question but I will elaborate with examples below. I have seen a lot of algorithms - for example, for ...
shole's user avatar
  • 1,200
74 votes
4 answers
33k views

(When) is hash table lookup O(1)?

It is often said that hash table lookup operates in constant time: you compute the hash value, which gives you an index for an array lookup. Yet this ignores collisions; in the worst case, every item ...
Gilles 'SO- stop being evil''s user avatar
63 votes
4 answers
20k views

Why are Red-Black trees so popular?

It seems that everywhere I look, data structures are being implemented using red-black trees (std::set in C++, SortedDictionary ...
Jakub Arnold's user avatar
50 votes
9 answers
16k views

Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface: Insert: insert an element into the structure Get-Min: return the smallest element in the structure Extract-Min: ...
Alex ten Brink's user avatar
45 votes
2 answers
31k views

What is the difference between radix trees and Patricia tries?

I am learning about radix trees (aka compressed tries) and Patricia tries, but I am finding conflicting information on whether or not they are actually the same. A radix tree can be obtained from a ...
w128's user avatar
  • 553
43 votes
2 answers
9k views

Efficient data structures for building a fast spell checker

I'm trying to write a spell-checker which should work with a pretty large dictionary. I really want an efficient way to index my dictionary data to be used using a Damerau-Levenshtein distance to ...
Charles Menguy's user avatar
42 votes
1 answer
2k views

Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

Let's assume the following definition of a red-black tree: It is a binary search tree. Each node is colored either red or black. The root is black. Two nodes connected by an edge cannot be red at the ...
alisianoi's user avatar
  • 419
38 votes
2 answers
28k views

Hash tables versus binary trees

When implementing a dictionary ('I want to look up customer data by their customer IDs'), the typical data structures used are hash tables and binary search trees. I know for instance that the C++ STL ...
Alex ten Brink's user avatar
35 votes
11 answers
13k views

Why is data in computer science considered to be discrete?

I understand that "structure" of data is totally dependent on Boolean Algebra, but: Why is data considered to be a discrete mathematical entity rather than a continuous one? Related to this: ...
evil_potato's user avatar
  • 1,362
34 votes
5 answers
4k views

Is there an anti-Bloom filter?

A Bloom filter makes it possible to efficiently keep track of whether various values have already been encountered during processing. When there are many data items then a Bloom filter can result in ...
András Salamon's user avatar
32 votes
3 answers
5k views

Will hardware/implementation affect the time/space complexity of algorithms?

I’m not even a CS student, so this might be a stupid question, but please bear with me... In the pre-computer era, we can only implement an array data structure with something like an array of ...
nalzok's user avatar
  • 1,091
30 votes
2 answers
9k views

Not all Red-Black trees are balanced?

Intuitively, "balanced trees" should be trees where left and right sub-trees at each node must have "approximately the same" number of nodes. Of course, when we talk about red-...
Aryabhata's user avatar
  • 6,261
29 votes
3 answers
15k views

Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
Rontogiannis Aristofanis's user avatar
28 votes
1 answer
48k views

Two definitions of balanced binary trees

I have seen two definitions of balanced binary trees, which look different to me. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number ...
forrestGump's user avatar
28 votes
1 answer
1k views

Is there a 'string stack' data structure that supports these string operations?

I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing ...
Alex ten Brink's user avatar
27 votes
2 answers
6k views

Data structure with search, insert and delete in amortised time $O(1)$?

Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time? GetElement(k): Return the $k$th element of the list. InsertAfter(x,y): Insert ...
A T's user avatar
  • 968
27 votes
2 answers
4k views

Efficient map data structure supporting approximate lookup

I'm looking for a data structure that supports efficient approximate lookups of keys (e.g., Levenshtein distance for strings), returning the closest possible match for the input key. The best suited ...
merijn's user avatar
  • 409
26 votes
1 answer
6k views

Why does the splay tree rotation algorithm take into account both the parent and grandparent node?

I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why ...
Bober02's user avatar
  • 383
25 votes
4 answers
9k views

Data Structure for Set Intersection?

Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated? Init an empty set. Add an ...
Dawei Huang's user avatar
24 votes
8 answers
4k views

Does every data type just boil down to nodes with pointers?

An array or vector is just a sequence of values. They can surely be implemented with a linked list. This is just a bunch of nodes with pointers to the next node. Stacks and queues are two abstract ...
derekchen14's user avatar
23 votes
4 answers
5k views

Why do we use persistent data structures in functional programming?

Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would ...
gpuguy's user avatar
  • 1,809
23 votes
3 answers
42k views

When are adjacency lists or matrices the better choice?

I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the ...
user21312's user avatar
  • 351
23 votes
1 answer
10k views

How many different max-heaps exist for a list of n integers?

How many different max-heaps exist for a list of $n$ integers? Example: list [1, 2, 3, 4] The max-heap can be either 4 3 2 1: ...
Pratik Deoghare's user avatar
23 votes
1 answer
1k views

Is there an equivalent of van Emde Boas trees for ropes?

Someone I know is planning on implementing a text editor in the near future, which prompted me to think about what kind of data structures are fast for a text editor. The most used structures are ...
Alex ten Brink's user avatar
23 votes
2 answers
3k views

What combination of data structures efficiently stores discrete Bayesian networks?

I understand the theory behind Bayesian networks, and am wondering what it takes to build one in practice. Let's say for this example, that I have a Bayesian (directed) network of 100 discrete random ...
rxmnnxfpvg's user avatar
23 votes
1 answer
5k views

How Does Populating Pastry's Routing Table Work?

I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify. Disclaimer: I'm not a computer science student. I've ...
Paddy's user avatar
  • 333
22 votes
3 answers
23k views

What is the purpose of using NIL for representing null nodes?

In my Algorithms and Data Structures course, professors, slides and the book (Introduction to Algorithms, 3rd edition) have been using the word NIL to denote for ...
user avatar
22 votes
2 answers
21k views

What is the advantage of heaps over sorted arrays?

I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default. And a follow ...
Nick Olinger's user avatar
22 votes
1 answer
5k views

AVL trees are not weight-balanced?

In a previous question there was a definition of weight balanced trees and a question regarding red-black trees. This question is to ask the same question, but for AVL trees. The question is, ...
Aryabhata's user avatar
  • 6,261
22 votes
4 answers
52k views

Increase-key and decrease-key in a binary min-heap

In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally ...
GatotPujo's user avatar
  • 221
21 votes
9 answers
11k views

Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
Dudi Frid's user avatar
  • 161
21 votes
1 answer
5k views

Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

I'm looking for a data structure that will push its oldest/last element out if a new element is inserted. For example, let D represent the structure. ...
Greg M's user avatar
  • 313
21 votes
12 answers
14k views

Data structure or algorithm for quickly finding differences between strings

I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the ...
JGut's user avatar
  • 321
21 votes
2 answers
20k views

Proving a binary heap has $\lceil n/2 \rceil$ leaves

I'm trying to prove that a binary heap with $n$ nodes has exactly $\left\lceil \frac{n}{2} \right\rceil$ leaves, given that the heap is built in the following way: Each new node is inserted via ...
varatis's user avatar
  • 463
21 votes
1 answer
2k views

What classes of data structures can be made persistent?

Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged ...
Realz Slaw's user avatar
  • 6,191
20 votes
5 answers
625 views

Efficient compression of unlabeled trees

Consider unlabeled, rooted binary trees. We can compress such trees: whenever there are pointers to subtrees $T$ and $T'$ with $T = T'$ (interpreting $=$ as structural equality), we store (w.l.o.g.) $...
Raphael's user avatar
  • 72.3k
20 votes
2 answers
902 views

Creating a Self Ordering Binary Tree

I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the ...
OghmaOsiris's user avatar
20 votes
2 answers
2k views

Are link-cut trees ever used in practice, for max flow computation or other applications?

Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as link-...
Rob Lachlan's user avatar
20 votes
1 answer
955 views

Supporting data structures for SAT local search

WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the ...
Juho's user avatar
  • 22.5k
20 votes
1 answer
1k views

Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
A T's user avatar
  • 968
19 votes
2 answers
17k views

What is the difference between abstract and concrete data structures?

I thought associative array (i.e. map, or dictionary) and hashing table were the same concept, until I saw in Wikipedia that For dictionaries with very small numbers of bindings, it may make ...
Tim's user avatar
  • 4,865
19 votes
1 answer
1k views

Saving on array initialization

I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. ...
Aryabhata's user avatar
  • 6,261
19 votes
5 answers
3k views

For what kind of data are hash table operations O(1)?

From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there ...
Gilles 'SO- stop being evil''s user avatar
19 votes
1 answer
887 views

Weighted sum of last N numbers

Suppose we're receiving numbers in a stream. After each number is received, a weighted sum of the last $N$ numbers needs to be calculated, where the weights are always the same, but arbitrary. How ...
Ambroz Bizjak's user avatar
19 votes
5 answers
1k views

Priority queue for partially ordered priorities with infima

I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield minimal item each time). But rather than ...
Jan Hudec's user avatar
  • 658
19 votes
1 answer
934 views

How does the runtime of the Ukkonen's algorithm depend on the alphabet size?

I am concerned with the question of the asymptotic running time of the Ukkonen's algorithm, perhaps the most popular algorithm for constructing suffix trees in linear (?) time. Here is a citation ...
Mikhail Dubov's user avatar
19 votes
2 answers
680 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
mnbvmar's user avatar
  • 373
19 votes
1 answer
450 views

Problems for which algorithms based on partition refinement run faster than in loglinear time

Partition refinement is a technique in which you start with a finite set of objects and progressively split the set. Some problems, like DFA minimization, can be solved using partition refinement ...
Juho's user avatar
  • 22.5k

1
2 3 4 5
44