Book Image

C# Data Structures and Algorithms

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms

By: Marcin Jamro

Overview of this book

Data structures allow organizing data efficiently. They are critical to various problems and 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. At the beginning, you will get to know arrays, lists, dictionaries, and sets together with real-world examples of your application. Then, you will learn how to create and use stacks and queues. In the following part of the book, the more complex data structures will be introduced, namely trees and graphs, together with some algorithms for searching the shortest path in a graph. We will also discuss how to organize the code in a manageable, consistent, and extendable way. By the end of the book,you will learn how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (14 chapters)

Red-black trees


A Red-black tree, also referred to as an RBT, is the next variant of the self-balancing binary search trees. As a variant of BSTs, this data structure requires that the standard BST rules be maintained. Moreover, the following rules must be taken into account:

  • Each node must be colored either red or black. Thus, you need to add additional data for a node that stores a color.
  • All nodes with values cannot be leaf nodes. For this reason, the NIL pseudo-nodes should be used as leaves in the tree, while all other nodes are internal ones. Moreover, all NIL pseudo-nodes must be black.
  • If a node is red, both its children must be black.
  • For any node, the number of black nodes on the route to a descendant leaf (that is, the NIL pseudo-node) must be the same.

The proper RBT is presented in the following diagram:

The tree consists of nine nodes, each colored red or black. It is worth mentioning the NIL pseudo-nodes, which are added as leaf nodes. If you again take a look at the set of rules...