Source code online books for professionals by professionals

reaLLY DIVIDING the WOrK: MULtIprOCeSSING
the purpose of the divide-and-conquer design method is to balance the workload so that each recursive call 
takes as little time as possible. You could go even further, though, and ship the work out to separate processors 
(or cores). if you have a huge number of processors to use, you could then, in theory, do nifty things such as 
finding the maximum or sum of a sequence in logarithmic time. (Do you see how?)
in a more realistic scenario, you might not have an unlimited supply of processors at your disposal, but if 
you’d like to exploit the power of those you have, the 
multiprocessing
 module can be your friend. parallel 
programming is commonly done using parallel (operating system) threads. although python has a threading 
mechanism, it does not support true parallel execution. What you can do, though, is use parallel processes, which 
in modern operating systems are really efficient. the 
multiprocessing
 module gives you an interface that makes 
handling parallel processes look quite a bit like threading.
Tree Balance ... and Balancing
*
If we insert random values into a binary search tree, it’s going to end up pretty balanced on average. If we’re unlucky, 
though, we could end up with a totally unbalanced tree, basically a linked list, like the one in Figure 
6-1
. Most real-world 
uses of search trees include some form of balancing, that is, a set of operations that reorganize the tree, to make sure it is 
balanced (but without destroying its search tree property, of course).
*
This section is a bit hard and is not essential in order to understand the rest of the book. Feel free to skim it or even skip it entirely. 
You might want to read the “Black Box” sidebar on binary heaps, heapq, and heapsort, though, later in the section.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
132
There’s a ton of different tree structures and balancing methods, but they’re generally based on two fundamental 
operations:
•  Node splitting (and merging). Nodes are allowed to have more than two children (and more 
than one key), and under certain circumstances, a node can become overfull. It is then split 
into two nodes (potentially making its parent overfull).
•  Node rotations. Here we still use binary trees, but we switch edges. If x is the parent of y, we 
now make y the parent of x. For this to work, x must take over one of the children of y.
This might seem a bit confusing in the abstract, but I’ll go into a bit more detail, and I’m sure you’ll see how it all 
works. Let’s first consider a structure called the 2-3-tree. In a plain binary tree, each node can have up to two children, 
and they each have a single key. In a 2-3-tree, though, we allow a node to have one or two keys and up to three children. 
Anything in the left subtree now has to be smaller than the smallest of the keys, and anything in the right subtree is 
greater than the greatest of the keys—and anything in the middle subtree must fall between the two. Figure 
6-10
 shows 
an example of the two node types of a 2-3-tree.