book

Grokking Algorithms, Second Edition

by Aditya Bhargava

March 2024

Beginner to intermediate

320 pages

7h 6m

English

Manning Publications

Read now

Unlock full access

forewordprefaceacknowledgmentsabout this bookabout the author
Binary searchBig O notationRecap
How memory worksArrays and linked listsWhich is used more, arrays or linked lists?Selection sortExample code listingRecap
RecursionBase case and recursive caseThe stackRecap

Divide and conquerQuicksortBig O notation revisitedRecap
Hash functionsUse casesCollisionsPerformanceRecap
Introduction to graphsWhat is a graph?Breadth-first searchImplementing the graphImplementing the algorithmRecap
Your first treeA space odyssey: Depth-first searchBinary treesHuffman codingRecap
A balancing actShorter trees are fasterAVL trees: A type of balanced treeSplay treesB-treesRecap
Working with Dijkstra’s algorithmTerminologyTrading for a pianoNegative-weight edgesImplementationRecap
The classroom scheduling problemThe knapsack problemThe set-covering problemRecap
The knapsack problem (revisited)Knapsack problem FAQLongest common substringRecap
Classifying oranges vs. grapefruitBuilding a recommendations systemRegressionIntroduction to machine learningA high-level overview of training an ML modelRecap
Linear regressionInverted indexesThe Fourier transformParallel algorithmsmap/reduceBloom filters and HyperLogLogHTTPS and the Diffie–Hellman key exchangeLocality-sensitive hashingMin heaps and priority queuesLinear programmingEpilogue
Decision problemsThe satisfiability problemHard to solve, quick to verifyReductionsNP-hardNP-completeRecap

Content preview from Grokking Algorithms, Second Edition

8 Balanced trees

In this chapter

You learn about a new data structure called binary search trees (BSTs).
You learn about balanced trees and why they often perform better than arrays or linked lists.
You also learn about AVL trees, a type of balanced BST. In the worst-case scenario, binary trees can be slow. A balanced tree will help them perform effectively.

In the last chapter, you learned about the new data structure, trees. Now that you and trees are best friends, it’s time to see what they are used for. When arrays and linked lists fail to deliver the desired performance, a good next step is to try a tree. In this chapter, we’ll discuss the performance that trees can offer. We’ll then explore a special type of tree that can offer exceptional ...