Introduction to Algorithms — Red-Black Tree

1. Properties of red-black trees

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can either RED or BLACK. By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Each node of the tree now contains the attributes color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL. We shall regard these NILs as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.

A red-black tree is a binary tree that satisfies the following red-black properties:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Screen Shot 2017-05-05 at 8.27.10 P

As a matter of convenient in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. For a red-black tree T, the sentinel T.nil is an object with the same attributes as an ordinary node in the tree.

  • Its color attribute is BLACK, and its other attributes — p, left, right, and key can take on arbitrary values.

As Figure (b) shows, all pointers to NIL are replaced by pointer to the sentinel T.nil.

We use the sentinel so that we can treat a NIL child of a node x as an ordinary node whose parent is x .

  • Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, that approach would waste space.
  • Instead, we use the one sentinel T.nil to represent all the NILs — all leaves and the root’s parent. The values of the attributes p, left, right, and key of the sentinel are immaterial, although we may set them during the course of a procedure for our convenience.

Screen Shot 2017-05-05 at 8.28.39 P

We generally confine our interest to the internal nodes of a red-black tree, since they hold the key values. In the remainder of this article, we omit the leaves when we draw red-black trees, as shown in (c).

Screen Shot 2017-05-05 at 8.30.02 P

We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x). By property 5, the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes. We define the black-height of a red-black tree to be the black-height of its root.

The following lemma shows why red-black tree make good search trees.

Lemma 1

A red-black tree with n internal nodes has height at most 2 \lg(n+1) .

proof:

As an immediate consequence of this lemma, we can implement the dynamic-set operations in O(\lg n) time on red-black trees, since each can run in O(h) time on a binary search tree of height h and any red-black tree on n nodes is a binary search tree with height O(\lg n) . Although the algorithms TREE-INSERT and TREE-DELETE in Binary Search Tree run in O(\lg(n)) time when given a red-black tree as input, they do not directly support the dynamic-set operations INSERT and DELETE, since they do not guarantee that the modified binary search tree will be a red-black tree.


2. Rotations

The search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black tree with n keys, take O(\lg n) time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 1. To restore these properties, we must change the colors of some the nodes in the tree and also change the pointer structure.

We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. Figure 2 shows the two kinds of rotations: left rotations and right rotations.

  • When we do a left rotation on a node x , we assume that its right child y is not T.nil ; x may be any node in the tree whose right child is not T.nil .
    • The left rotation “pivots” around the link from x to y . It makes y the new root of the subtree, with x as y ‘s left child and y ‘s left child as x ‘s right child.

The pseudocode for LEFT-ROTATE assumes that x.right \neq T.nil and that the root’s parent is T.nil .

fig_13-2

LEFT-ROTATE(T, x)
  

Figure 3 shows an example of how LEFT-ROTATE modifies a binary search tree. The code for RIGHT-ROTATE is symmetirc. Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time. Only pointers are changed by a rotation; all other attributes in a node remain the same.

fig_13-3

3. Insertion

We can insert a node into an n -node red-black tree in O(\lg(n)) time. To do so, we use a slightly modified version of the TREE-INSERT procedure to insert node z into the tree T as if it were an ordinary binary search tree, then we color z red. To guarantee that the red-black properties are preserved, we then call an auxiliary procedure RB-INSERT-FIXUP to recolor node and perform rotations. The call RB-INSERT(T, z) inserts node z , whose keys is assumed to have already been filled in, into the red-black tree T .

RB-INSERT(T, z)
  

The procedures TREE-INSERT and RB-INSERT differ in four ways.

  • First, all instance of NIL in TREE-INSERT are replaced by T.nil.
  • Second, we set z.left and z.right to T.nil in lines 14-15 of RB-INSERT, in order to maintain the proper tree structure.
  • Third, we color z red.
  • Fourth, because coloring z red may cause a violation of one of the red-black properties, we call RB-INSERT-FIXUP(T, z) of RB-INSERT to restore the red-black properties.
RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED
            z.p.color = BLACK           // case 1
            y.color = BLACK             // case 1
            z.p.p.color = RED           // case 1
            z = z.p.p                   // case 1
        else if z == z.p.right
                  z = z.p               // case 2
                  LEFT-ROTATE(T, z)     // case 2
        else
            z.p.color = BLACK           // case 3
            z.p.p.color = RED           // case 3
            RIGTH-ROTATE(T, z.p.p)      // case 3
    else (same as then clause with "right" and "left" exchanged)
  T.root.color = BLACK            

To understand how RB-INSERT-FIXUP works, we shall our examination of the code in three major steps.

  • First, we shall determine what violations of the red-black properties are introduced in RB-INSERT when node z is inserted and colored red.
  • Second, we shall examine the overall goal of the while loop in line 1-15.
  • Finally, we shall explore each of the three cases within the while loop’s body and see how they accomplish the goal.

Figure 4 shows how RB-INSERT-FIXUP operates on a sample red-black tree.

fig_13-4


4. Deletion

RB-DELETE-FIXUP(T, x)

Introduction-to-algorithms — dynamic programmimng

Dynamic programming typically applies to optimization problems in which we make a set of choices in order to arrive at an optimal solution. As we make each choice, subproblems of the same form often arise. Dynamic programming is effective when a given subproblem may arise form more than one partial set of choices.

  • The key technique is to store the solution to each such subproblem in case it should reappear.

Divide-and-conquer algorithms portion the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem — that is, when subproblems share subsubproblems.

  • In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly, solving the common subsubproblems.

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

  1. Characterize the structure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute the value of an optimal solution, typically in a bottom-up fashion.
  4. Construct an optimal solution from computed information.

Step 1-3 from the basis of a dynamic-programming solution to a problem.

  • If we need only the value of an optimal solution, and not the solution itself, the we can omit step 4.
  • When we do perform step 4, we sometimes maintain additional information during step 3 so that we can easily construct an optimal solution.

Read More »

Performance of Python Data Structures

It is important for you to understand the efficiency of these Python data structures because they are the building blocks we will use as we implement other data structure in the remainder of the book.

Lists

The designers of Python had many choices to make when they implemented the list data structure. Each of these choices could have an impact of how fast on how fast list operations perform. To help them make the right choices they looked at the ways that people would most commonly use the list data structure and they optimized their implementation of a list so that the most common operations were very fast. Of course they also tried to make the less common operations fast, but when a tradeoff and to be made the performance of a less common operation was often sacrificed in favor of the more common operation.

Two common operations are indexing and assigning to an index position. Bothe of these operations take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list they are O(1) .

Read More »

Mathematics for 3D Game Programming and Computer Graphics – Vectors

Vectors are of fundamental importance in any 3D game engine. They are used to represent points in space, such as the locations of objects in a game or the vertices of a triangle mesh. They are also used to represent spatial directions, such as the orientation of the camera or the surface normals of a triangle mesh. Understanding how to manipulate vectors is an essential skill of the successful 3D programmer.

Throughout this book, we encounter vectors of various types, usually representing two-dimensional, three-dimensional, or four-dimensional quantities. For now, we make no distinction between vectors representing options and vectors representing directions, nor do we concern ourselves with how vectors are transformed from one coordinate system to another.

Vector Properties

The Dot Product

The dot product of two vectors, also known as the scalar product or inner product, is one of the most heavily used operations in 3D graphics because it supplies a measure of the difference between the directions in which the two vectors point.

\mathbf{P} \cdot \mathbf{Q} = \sum_{i=1}^{m} P_i Q_i.

This definition states that the dot product of two vectors is given by the sum of the products of each component. In three dimensions, we have

\mathbf{P} \cdot \mathbf{Q} = P_x Q_x + P_y Q_y + P_z Q_z.

The dot product P \cdot Q may also be expressed as the matrix product:

\mathbf{P}^T \mathbf{Q} = \begin{bmatrix}P_1 & P_2 & \cdots & P_n\end{bmatrix} \begin{bmatrix} Q_1 \\ Q_2 \\ \vdots \\ Q_n \end{bmatrix},

Now for an important theorem that reveals the ubiquitous utility of the dot product.

Given two n -dimensional vectors \mathbf{P} and \mathbf{Q} , the dot product \mathbf{P} \cdot \mathbf{Q} satisfies the equation

\mathbf{P} \cdot \mathbf{Q} = \lVert P \rVert \lVert Q \rVert \cos \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by \mathbf{P} and \mathbf{Q} .

The Cross Product

The cross product of two three-dimensional vectors, also known as the vector product, returns a new vector that is perpendicular to both of the vectors being multiplied together. This property has many uses in computer graphics, one of which is a method for calculating a surface normal at a particular point given two distinct tangent vectors.

The cross product of two 3D vectors P and Q , written as P \times Q , is a vector quantity given by the formula:

P \times Q = < P_yQ_z - P_zQ_y, P_zQ_x - P_xQ_z, P_xQ_y - P_yQ_x >

A commonly used tool for remembering this formula is to calculate cross products by evaluating the pseudodeterminant

P \times Q = \begin{vmatrix} i & j & k \\ P_x & P_y & P_z \\ Q_x & Q_y & Q_z \end{vmatrix}

Theorem 2.8

\lVert P \times Q \rVert = \lVert P \rVert \lVert Q \rVert \sin \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by P and Q .

We know that any nonzero result of the cross product must be perpendicular to the two vectors being multiplied together, but there are two possible directions that satisfy this requirement. It turns out that the cross product follows a pattern called the right hand rule.

Mathematics for 3D Game Programming and Computer Graphics – The render pipeline

This chapter provides a preliminary review of the rendering pipeline. It covers general functions, such as vertex transformation and primitive rasterization, which are performed by modern 3D graphics hardware. Readers who are familiar with these concepts may safely skip ahead. We intentionally avoid mathematical discussions in this chapter and instead provide pointers to other parts of the book where each particular portion of the rendering pipeline is examined in greater detail.

Graphics Processors

A typical scene that is to be rendered as 3D graphics is composed of many separate objects. The geometrical forms of these objects are each represented by a set of vertices and a particular type of graphics primitive that indicates how the vertices are connected to produce a shape. Figure 1.1 illustrates the ten types of graphics primitive defined by the OpenGL library. Graphics hardware is capable of rendering a set of individual points, a series of line segments, or a group of filled polygons. Most of the time, the surface of a 3D model is represented by a list of triangles, each of which references three points in a list of vertices.

f0002-01

Read More »

Getting MEAN – Designing a MEAN stack architecture

A common MEAN stack architecture

A common way to architect a MEAN stack application is to have a representational state transfer (REST) API feeding a single-page application (SPA). The API is typically built with MongoDB, Express, and Node.js, with the SPA being built in Angular. The approach is particularly popular with those who come to the MEAN stack from an Angular background and are looking for a stack that gives a fast, responsive API. Figure 2.1 illustrates the basic setup and data flow.

fig_2-1

What is a REST API?

REST stands for REpresentational State Transfer, which is an architectural style rather than a strict protocol. REST is stateless – it has no idea of any current user state or history.

API is an abbreviation for application program interface, which enables applications to take to each other.

So a REST API is a stateless interface to your application. In the case of the MEAN stack, the REST API is used to create a stateless interface to your database, enabling a way for other applications to work with the data.

Figure 2.1 is a great setup, ideal if you have or intend to build an SPA as your user-facing side.

  • Angular is designed with a focus on building SPAs, pulling in data from a REST API, as well as pushing it back.
  • MongoDB, Express, and Node.js are also extremely capable when it comes to building an API, using JSON all the way through the stack, including the database itself.

This is where many people start with the MEAN stack, looking for an answer to the question, "I've built an application in Angular; now where do I get the data?"

Read More »

Getting MEAN – Introducing full-stack development

The MEAN stack is a pure JavaScript stack comprised of four main technologies, with a cast of supporting technologies:

  • MongoDB — the database
  • Express — the web framework
  • Angular — the front-end framework
  • Node.js — the web server

Why the MEAN stack specifically?

The MEAN stack pulls together some of the "best-of-breed" modern web technologies into a very powerful and flexible stack. One of the great things about the MEAN stack is that it not only uses JavaScript in the browser, it uses JavaScript throughout. Using the MEAN stack, you can code both the front end and back end in the same language.

The principle technology allowing the this to happen is Node.js, bringing JavaScript to the back end.

Read More »

TypeScript as a language for Angular applications

The reason is that developing in JavaScript isn’t overly productive. Say a function expects a string value as an argument, but the developer mistakenly invokes it by passing a numeric value. With JavaScript, this error can be caught only at run- time. Java or C# compilers won’t even compile code that has mismatching types, but JavaScript is forgiving because it’s a dynamically typed language.

On larger projects, good IDE context-sensitive help and support for refactoring are important. Renaming all occurrences of a variable of function name in spatially typed languages is done by IDEs in a split second, even in projects that have thousands oaf lines of code; but this isn’t the case in JavaScript, which doesn’t support types. IDEs can help with refactoring much better when the types of the variables are known.

To be more productive, you may consider developing in a statically typed language and then convert the code to Javascript for deployment. Currently there are dozens of languages that compile to JavaScript. The most popular are TypeScript, CoffeeScript, and Dart.

Why not use the Dart language?

  • Interoperability with third-party Javascript libraries isn’t that great.
  • Development in Dart can be done only in a specialized version of the Chrome browser (Dartium) that comes with the Dart VM.
  • The generated JavaScript isn’t easily readable by a human.
  • The community of Dart developers is rather small.

Read More »

JavaScript definite guide – Arrays

An array is an ordered collection of values. Each value is called an element, and each element has a numeric position in the array, known as its index.

  • JavaScript arrays are untyped: an array element may be of any type, and different elements of the same array may be of different types. Array elements may even by objects o other arrays, which allows you to create complex data structures, such as arrays of objects and arrays of arrays.
  • JavaScript arrays are zero-based and use 32-bit indexes: the index of the first element is 0, and the highest possible index is 4294967294 (2^32−2 ), for a maximum as needed and there is no need to declare a fixed size for the array when you create it or to reallocate it when the size changes.
  • JavaScript arrays may be sparse: the elements need not have contiguous indexes and there may be gaps.
  • Every JavaScript array has a length property.
    • For non sparse arrays, this property specifies the number of elements in the array.
    • For sparse arrays, length is larger than the index of all elements.

JavaScript arrays are specialized form of JavaScript object, and array indexes are really little more than property names that happen to be integers. Implementations typically optimize arrays so that access to numerically indexed array elements is generally significantly faster than access to regular object properties.


Inner link

iOS development with Swift 3 – Your first iOS app

What is Swift?

Swift is the modern language created by Apple which got the Apple developer world buzzing. While loved by iOS developers, Objective-C was at the same time seen by many others as an outmoded language – a verbose and peculiar syntax, and with an unsafe type system. Built as a modern alternative to Objective-C, Swift was designed with specific enhancements in mind, specifically safety, performance, and expressiveness.

  • _Safety_ — Swift introduced several programming concepts to reduce some common programmer mistakes. These include strong typing, optionals and error handling.
  • _Performance_ — Apple has introduced internal optimizations to ensure that Swift runs fast. Xcode also provides warnings to encourage you to write code that ensures your app is running optimally.
  • _Expressiveness_ — Expressive code has the right balance between containing a clear meaning and being succinct.

Read More »