algorithms/RedBlackTrees.html at master · rakshitsareen/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
<html>
    <head>
        <link href="style.css" rel="stylesheet" type="text/css"/>
        <title>
            Design and Analysis of Algorithms: Red-Black Trees
        </title>
    </head>

    <body>
    <div id="header">
        <div id="logo">
            <img src="graphics/Julia.png">
        </div>
        <div id="user-tools">
            <a href="index.html">Home</a>
            &nbsp; &nbsp;
            <a href="about.html">About</a>
            &nbsp; &nbsp;
            <a href="feedback.html">Feedback</a>
        </div>
    </div>

        <h1>
            Design and Analysis of Algorithms: Red-Black Trees
        </h1>

            <div style="text-align:center">
                <p>
                <img
                 src="https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/500px-Red-black_tree_example.svg.png">
                </p>
            </div>

            <h2>
                What is a red-black tree?
            </h2>

                <p>
                    The colors (indeed, using any color at all -- we could call
                    them 0 and 1 trees!) are arbitrary. One story from one of
                    the creators is that they had red and black pens handy!
                </p>

                <h3>
                    Red-black properties
                </h3>

                    <ol>
                        <li>Every node is red or black.
                        </li>
                        <li>The root is black.
                        </li>
                        <li>Every leaf (<i>T.nil</i>) is black.
                        </li>
                        <li>If a node is red, then both of its children are
                            black. (Never two reds in a row while descending!)
                        </li>
                        <li>For each node, all paths from the node to its
                            descendant leaves contain the same number of black
                            nodes.
                        </li>
                    </ol>

                    <p>
                        And so, a simple way to get an intuition as
                        to why no leaf is further than
                        twice as far from the root as the nearest leaf: The
                        nearest leaf is B levels from the root. Since there is
                        never more than one R-node between any two B-nodes, at
                        most, the furthest node can be 2B - 1 levels away from
                        the root.
                    </p>

                <h2>
                    Operations on red-black trees
                </h2>

                    <p>
                        <b>Remember:</b> This <i>is</i> a binary search tree.
                        <br>
                        So, non-modifying operations such as minimum(),
                        maximum(), successor(), predecessor(), and search() run
                        in O(height) time, and so for red-black trees, in O(lg
                        n) time.
                        <br>
                        <br>
                        But what about insert and delete? They are obviously
                        trickier. In fact, they are the whole trick: the
                        red-black properties are just a way of keeping the tree
                        roughly balanced.
                    </p>


            <h2>
                Source Code
            </h2>

            <p>
            </p>
            <h2>
                For Further Study
            </h2>
                <ul>
                    <li><a
                href="https://www.cs.usfca.edu/~galles/visualization/RedBlack.html">
                            Red-black tree visualizer
                        </a>
                    </li>
                    <li><a href="https://en.wikipedia.org/wiki/Red–black_tree">
                            Wikipedia page on red-black trees
                        </a>.
                    </li>
                </ul>

            <h2>
                Homework
            </h2>
    </body>
    <script>
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
        ga('create', 'UA-97026578-2', 'auto');
        ga('send', 'pageview');
    </script>
</html>