Packt+ | Advance your knowledge in tech

0

All Products

Best Sellers

New Releases

Books

Videos

Audiobooks

Free Learning

Learning Functional Data Structures and Algorithms

You're reading from Learning Functional Data Structures and Algorithms Learn functional data structures and algorithms for your applications and bring their benefits to your work now

Product type Paperback

Published in Feb 2017

Publisher Packt

ISBN-13 9781785888731

Length 318 pages

Edition 1st Edition

Languages

Scala

Concepts

Data Structures and Algorithms

Authors (2):

S. Khot

Mishra

View More author details

Table of Contents (20) Chapters

Learning Functional Data Structures and Algorithms

Credits

About the Authors

About the Reviewer

www.PacktPub.com

Customer Feedback

Preface

1. Why Functional Programming? FREE CHAPTER

2. Building Blocks

3. Lists

4. Binary Trees

5. More List Algorithms

6. Graph Algorithms

7. Random Access Lists

8. Queues

9. Streams, Laziness, and Algorithms

10. Being Lazy - Queues and Deques

11. Red-Black Trees

12. Binomial Heaps

13. Sorting

Almost balanced trees

In the tree we just saw, every node's left and right subtrees are of the same height. This makes it a tree that is perfectly height-balanced. However, such trees are very rare; we come across them only when we have large trees with thousands of nodes.

Instead, we could try for trees that are either perfectly height-balanced or somewhere close to that. What do we mean by height-balanced? If the heights of any nodes, left or right subtrees, differ by at most 1, it is a height-balanced tree. The complexities of various operations would be almost the same as for a perfectly balanced tree.

In the preceding diagram, the left tree is height-balanced, whereas the right tree is not. In the left tree, the height of subtrees rooted at n is 1. The height of the subtree rooted at p is 0. These differ by 1, but we are okay with this little bit of imbalance.

The rest of the chapter is locked

Register for a free Packt account to unlock a world of extra content!

A free Packt account unlocks extra newsletters, articles, discounted offers, and much more. Start advancing your knowledge today.

Unlock this book and the full library FREE for 7 days

Get unlimited access to 7000+ expert-authored eBooks and videos courses covering every tech area you can think of

Start free trial

Renews at $15.99/month. Cancel anytime

Authors (2)

S. Khot

S. Khot

Atul S. Khot is a self-taught programmer and has written software programmes in C and C++. Having extensively programmed in Java and dabbled in multiple languages, these days, he is increasingly getting hooked on Scala, Clojure, and Erlang. Atul is a frequent speaker at software conferences and a past Dr. Dobb's product award judge. He was the author of Scala Functional Programming Patterns and Learning Functional Data Structures and Algorithms, published by Packt Publishing.

See other products by S. Khot

Mishra

Mishra

Raju Kumar Mishra is a consultant and corporate trainer for big data and programming. After completing his B. Tech from the Indian Institute of Technology (ISM) Dhanbad, he worked for Tata Steel. His deep passion for mathematics, data science, and programming took him to the Institute of Science (IISc). After graduating from IISc in computational science, he worked for Oracle as a performance engineer and software developer. He is an Oracle-certified associate for Java 7. He is a Hortonworks-certified Apache Hadoop Java developer, and holds a Developer Certification for Apache Spark (O'Reilly School of Technology and Databriks), and Revolution R Enterprise-certified Specialist Certifications. As well as this, he has also passed the Financial Risk Manager (FRM I) exam. His interest in mathematics helped him in clearing the CT3 (Actuarial Science) exam.

See other products by Mishra

Other recommended products

Related to this chapter

Java 9 Data Structures and Algorithms

Java 9 Data Structures and Algorithms

Java 9 has come out with several fantastic features including significant performance improvements, making it faster than ever. This book will teach you to organize data in an efficient way while exploiting the new features of Java 9 data structures.

Apr 2017 11h 20m

PHP 7 Data Structures and Algorithms

PHP 7 Data Structures and Algorithms

PHP has always been the the go-to language for web based application development, but there are materials and resources you can refer to to see how it works. Data structures and algorithms help you to code and execute them effectively, cutting down on processing time significantly. If you want to explore data structures and algorithms in a practical way with real-life projects, then this book is for you.

May 2017 11h 20m

C# Data Structures and Algorithms

C# Data Structures and Algorithms

Data structures allow organizing data efficiently. Their suitable implementation can provide a complete solution that acts like reusable code. In this book, you will learn how to use various data structures while developing in the C# language as well as how to implement some of the most common algorithms used with such data structures.

Apr 2018 9h 44m

C++ Data Structures and Algorithms

C++ Data Structures and Algorithms

C++ is a general-purpose programming language which has evolved over the years and is used to develop software for many different sectors. This book will be your companion as it takes you through implementing classic data structures and algorithms to help you get up and running as a confident C++ programmer.

Apr 2018 10h 44m

Beginning Java Data Structures and Algorithms

Beginning Java Data Structures and Algorithms

Learning about data structures and algorithms gives you a better insight on how to solve common programming problems. Most of the problems faced everyday by programmers have been solved, tried, and tested. By knowing how these solutions work, you can ensure that you choose the right tool when you face these problems. This book teaches you tools that you can use to build efficient applications. It starts with an introduction to algorithms and big O notation, later explains bubble, merge, quicksort, and other popular programming patterns. You'll also learn about data structures such as binary trees, hash tables, and graphs. The book progresses to advanced concepts, such as algorithm design paradigms and graph theory. By the end of the book, you will know how to correctly implement common algorithms and data structures within your applications.

Jul 2018 6h 44m

Hands-On Data Structures and Algorithms with Kotlin

Hands-On Data Structures and Algorithms with Kotlin

Data structures and algorithms help you to understand computational complexity and write efficient code. Kotlin data structures and algorithms enable you to write code that runs faster which is important in the web and mobile world. This book takes you through the techniques that you can use in your regular production environment.

Feb 2019 7h 20m

Professional Scala

Professional Scala

This book teaches you how to build and contribute to Scala programs, recognizing common patterns and techniques used with the language. You'll learn how to write concise, functional code with Scala. After an introduction to core concepts, syntax, and writing example applications with scalac, you'll learn about the Scala Collections API and how the language handles type safety via static types out-of-the-box. You'll then learn about advanced functional programming patterns, and how you can write your own Domain Specific Languages (DSLs). By the end of the book, you'll be equipped with the skills you need to successfully build smart, efficient applications in Scala that can be compiled to the JVM.

Jul 2018 6h 12m

Haskell Cookbook

Haskell Cookbook

Haskell is a purely functional language that has the great ability to develop large and difficult softwares that are easily maintainable. Haskell Cookbook provides recipes that start by illustrating the principles of functional programming in Haskell, and then gradually build up your expertise in creating industrial strength programs to accomplish any goal.

Sep 2017 13h 12m

Learning Scala Programming

Learning Scala Programming

Scala is a general purpose programming language that supports both functional and object-oriented programming paradigms. Due to its concise design and versatility, Scala's applications have been extended to a wide variety of fields such as data science and cluster computing.You will learn to write highly scalable, concurrent, and testable programs to meet everyday software requirements.

Jan 2018 14h 12m

Hands-On Data Structures and Algorithms with Python

Hands-On Data Structures and Algorithms with Python

Data structures help us to organize and align the data in a very efficient way. This book will surely help you to learn important and essential data structures through Python implementation for better understanding of the concepts.

Oct 2018 13h 16m

Hands-On Data Structures and Algorithms with Rust

Hands-On Data Structures and Algorithms with Rust

Hands-On Data Structures and Algorithms with Rust will help you in upgrading your earlier knowledge of Rust so that you shift to a confident developer by implementing the algorithms in a practical environment. This would be an essential reference guide for end-user/reader to understand the fundamental techniques of Rust. This guide will cover some of the major algorithms and data structures that will help the reader to interpret Rust in a practical way.

Jan 2019 10h 32m

Learning JavaScript Data Structures and Algorithms

Learning JavaScript Data Structures and Algorithms

A data structure is a particular way of organizing data in a computer to utilize resources efficiently. Data structures and algorithms are the base of every solution to any programming problem. With this book, you will learn to write complex and powerful code using the latest ES 8 features.

Apr 2018 14h 12m

Personalised recommendations for you

Based on your interests and search pattern

LLVM Code Generation

LLVM Code Generation

LLVM is a key technology for building modern compilers. You'll learn how to use its infrastructure to create and extend backends (X86 and AArch64), and contribute to the LLVM open-source project, equipping you with key skills in compiler design.

May 2025 20h 40m

Domain-Driven Refactoring

Domain-Driven Refactoring

This book is your exhaustive guide to applying DDD practices for building robust applications. You'll learn key patterns, refine business logic, and solve real-world problems with DDD principles, refactoring, and event-driven architectures.

May 2025 10h 48m

The Power Platform Playbook for Digital Transformation

The Power Platform Playbook for Digital Transformation

Transform your business with Power Apps, Power Automate, Power BI, and Copilot Studio. This guide covers automation, AI insights, governance, and security, helping leaders, IT pros, and analysts build scalable, low-code enterprise solutions.

Apr 2025 11h 44m

Microservices with Go

Microservices with Go

The book covers Go microservice development, covering the basics for beginners and best practices for structuring Go apps. Novice as well seasoned developers will gain insights into managing and scaling microservices.

Jun 2025 14h 16m