Introduction to Computational Thinking: Problem Solving, Algorithms, Data Structures, and More

© The Author(s), under exclusive license to APress Media, LLC, part of Springer Nature 2021

T. MailundIntroduction to Computational Thinkinghttps://doi.org/10.1007/978-1-4842-7077-6_15

15. Red-Black Search Trees

Thomas Mailund¹  

(1)

Aarhus N, Denmark

 

There are many strategies for balancing search trees to ensure logarithmic running time for their operations. All the approaches involve modifying them when you insert or delete elements and rebalancing them to minimize their height, and in this chapter, I will show you one technique: the red-black search trees. It is a search tree where we add one of two colors to each node, either red or black:

RED = 0

BLACK = 1

class Node(object):

    def __init__(self, value,

                 colour = RED,

                 left ...