Еще

Грокаем структуры данных

18+

Ваша оценка

3

(1)

Грокаем структуры данных

Цитаты из книги Грокаем структуры данных

fru-n-quiz
22 марта 2026
Linear and quadratic probing (in open addressing) often produce element clusters, long chains that must be traversed during search and insertion, thus slowing down these operations.
4
fru-n-quiz
22 марта 2026
now it’s time to address the “elephant in the table.”
2
fru-n-quiz
22 марта 2026
This makes BBSTs the data structure with the best average performance across the full range of operations: there are some operations where a sorted array or a linked list might be faster, but the average over all operations favors BBSTs (balanced binary search trees).
2
fru-n-quiz
22 марта 2026
The most used balanced search trees are, however, red–black trees and 2–3 trees. You can read more about them in in chapter 3 of Advanced Algorithms and Data Structures (La Rocca, 2021, Manning), or in chapter 13 of Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein, 2022, MIT Press),
2
fru-n-quiz
22 марта 2026
are we doomed?
1
fru-n-quiz
22 марта 2026
In the first example, we add a duplicate of the value at the root of the tree, 6. At the root, we go left, as we always do when we find the same value as the one stored in a node. We traverse this branch until we reach the leaf with the value 5, and we know we can add our new node there.
<…>
In the other case presented, we add the largest value yet in the tree, so we traverse a path to the far right of the tree, and there we add a new node for the value 11.
9
fru-n-quiz
22 марта 2026
These trees are designed to make search fast, potentially as fast as binary search on a sorted array. And they have one important advantage over sorted arrays: insertion and deletion can be faster on a BST. What’s the catch, and what’s the tradeoff? Like linked lists, trees require more memory to implement, and their code is more complex, especially if we want to guarantee that these operations are faster than on arrays.
2
fru-n-quiz
22 марта 2026
Trees are used in machine learning, and decision trees and random forests are some of the best nonneural network classification tools. We have discussed the heap <…>, which is a special tree that efficiently implements priority queues. There are many more specialized trees, such as b-trees, which are used to store data efficiently (like in databases), or kd-trees, which allow the indexing of multidimensional data. But these are just the tip of the iceberg: trees are a very large class of extremely versatile data structures.
Читать далее
2
fru-n-quiz
22 марта 2026
in a binary tree, a node may have zero, one, or two child links. We usually label these two links: we have the left and right children of a node, and thus its left and right subtrees.
2
fru-n-quiz
22 марта 2026
Some other mornings, I feel a little down, and I add sugar to my cereal to sweeten up my day. And sometimes, when I’m feeling mopey, I skip the cereal altogether and go straight for the ice cream bucket!
6
fru-n-quiz
21 марта 2026
When a node has no links to children, it’s called a leaf.
4
fru-n-quiz
21 марта 2026
When the requesters can afford a slower (non-real-time) response, we can regulate the pace of a web service by using the so-called pull strategy and a queue.
4
fru-n-quiz
21 марта 2026
I’ll go for a cleaner (although arguably less efficient) way—we can use the modulo operator to map virtual indexes into the physical indexes of the array,
2
fru-n-quiz
20 марта 2026
While stacks use the LIFO (last in, first out) policy, queues abide by a symmetric principle, called FIFO, which stands for first in, first out. FIFO means that when we consume an element from a queue, the element will always be the one that has been stored the longest, and it is the only one we can remove.
6
fru-n-quiz
20 марта 2026
If your gut instinct tells you that this must be terribly inefficient, you are right: it requires twice as much memory (two stacks of the same size, one of which is kept empty),
<…>
But sometimes you might have no choice: when life gives you stacks…
5
fru-n-quiz
15 марта 2026
dynamic arrays can be implemented by using static arrays underneath and seamlessly (to the client) resizing these arrays as needed.
7
fru-n-quiz
14 марта 2026
for loops are multipliers, meaning that the cost of the instructions inside the loop must be multiplied by the number of iterations.
15
fru-n-quiz
14 марта 2026
There can be many resources you may want to measure, depending on the context, but in this book, we focus on two. <…> we are interested in running time to understand how long it will take for an algorithm to compute its result.
<…>
The other critical resource is memory.
9
fru-n-quiz
14 марта 2026
If we run a large number of operations, however, we can amortize the cost of the single unlucky operation by spreading it over the total time taken by all the operations. In fact, this is what we call amortized analysis.
18
fru-n-quiz
14 марта 2026
Now that we have defined a computational model for studying algorithms, we are ready to introduce the actual metrics we use. Yes, that means this is the math part! But don’t worry! We are going to take a visual approach and greatly simplify the notation used—we are going to define and use it very informally.
2

Показаны цитаты 41–60 из 68

1
2
3
4