Data Structures and Algorithms in Swift: Implement Stacks, Queues, Dictionaries, and Lists in Your Apps

© Elshad Karimov 2020

E. KarimovData Structures and Algorithms in Swifthttps://doi.org/10.1007/978-1-4842-5769-2_12

12. Red–Black Tree

Elshad Karimov¹ 

(1)

New York, New York, USA

 

A red–black tree (RBT) is a type of Binary Search Tree where a new parameter – color for each node – has been defined (Figure 12-1). We learned that after some insert and delete operations, the Binary Search Trees become unbalanced which creates a linked list. Red–black trees solve this problem by balancing elements. Each node has a color which can be black or red. Thus, when declaring a node for the RBT, it must contain a key/value, a color, the reference to a parent node, and the references for the children nodes. RBTs are very useful for worst-case scenarios when processing ...