text:
Binary tree

In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree with $k = 2$. A recursive definition using set theory is that a binary tree is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

From a graph theory perspective, binary trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence, a term which appears in some early programming books before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.

In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.

In computing, binary trees can be used in two very different ways:

 * First, as a means of accessing nodes based on some value or label associated with each node. Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting. The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular, it is significant in binary search trees. However, the arrangement of particular nodes into the tree is not part of the conceptual information. For example, in a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by balancing) without changing the meaning.
 * Second, as a representation of data with a relevant bifurcating structure. In such cases, the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with Huffman coding and cladograms. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.

Recursive definition
To define a binary tree, the possibility that only one of the children may be empty must be acknowledged. An artifact, which in some textbooks is called an extended binary tree, is needed for that purpose. An extended binary tree is thus recursively defined as:
 * the empty set is an extended binary tree
 * if T1 and T2 are extended binary trees, then denote by T1 • T2 the extended binary tree obtained by by adding edges when these sub-trees are non-empty.

Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.

Using graph theory concepts
A binary tree is a rooted tree that is also an ordered tree (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root); thus, for every node, a notion of children may be defined as the nodes connected to it a level below. Ordering of these children (e.g., by drawing them on a plane) makes it possible to distinguish a left child from a right child. But this still does not distinguish between a node with left but not a right child from a node with right but no left child.

The necessary distinction can be made by first partitioning the edges; i.e., defining the binary tree as triplet (V, E1, E2), where (V, E1 ∪ E2) is a rooted tree (equivalently arborescence) and E1 ∩ E2 is empty, and also requiring that for all j ∈ { 1, 2 }, every node has at most one Ej child. A more informal way of making the distinction is to say, quoting the Encyclopedia of Mathematics, that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees.

Types of binary trees
Tree terminology is not well-standardized and so varies in literatures.
 * A  binary tree has a root node and every node has at most two children.
 * A  binary tree (sometimes referred to as a proper, plane, or strict binary tree) is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a recursive definition. A full binary tree is either:
 * A single vertex (a single node as the root node).
 * A tree whose root node has two subtrees, both of which are full binary trees.
 * A  binary tree is a binary tree in which all interior nodes have two children and all leaves have the same depth or same level (the level of a node defined as the number of edges or links from the root node to a node). A perfect binary tree is a full binary tree.
 * A  binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h. A perfect tree is therefore always complete but a complete tree is not always perfect. Some authors use the term complete to refer instead to a perfect binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.  A complete binary tree can be efficiently represented using an array.

 * The infinite complete binary tree is a tree with $${\aleph_0}$$ levels, where for each level d the number of existing nodes at level d is equal to 2d. The cardinal number of the set of all levels is $${\aleph_0}$$ (countably infinite). The cardinal number of the set of all paths (the "leaves", so to speak) is uncountable, having the cardinality of the continuum.
 * A balanced binary tree is a binary tree structure in which the left and right subtrees of every node differ in height (the number of edges from the top-most node to the farthest node in a subtree) by no more than 1 (or the skew is no greater than 1). One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther". )
 * A degenerate (or pathological) tree is where each parent node has only one associated child node. This means that the tree will behave like a linked list data structure. In this case, an advantage of using a binary tree is significantly reduced because it is essentially a linked list which time complexity is O(n) (n as the number of nodes) and it has more data space than the linked list due to two pointers per node, while the complexity of O(log2n) for data search in a balanced binary tree is normally expected.

Properties of binary trees

 * The number of nodes $$n$$ in a full binary tree is at least $$2h+1$$ and at most $$2^{h+1}-1 $$ (i.e., the number of nodes in a perfect binary tree), where $$h$$ is the height of the tree. A tree consisting of only a root node has a height of 0. The least number of nodes is obtained by adding only two children nodes per adding height so $$2h+1$$ (1 for counting the root node). The maximum number of nodes is obtained by fully filling nodes at each level, i.e., it is a perfect tree. For a perfect tree, the number of nodes is $$1 + 2 + 4 + \ldots + 2^h = 2^{h + 1} - 1$$, where the last equality is from the geometric series sum.
 * The number of leaf nodes $$l$$ in a perfect binary tree is $$l = (n + 1) / 2$$ (where $$n$$ is the number of nodes in the tree) because $$n={{2}^{h+1}}-1$$ (by using the above property) and the number of leaves is $$2^h$$ so $$n=2\cdot {{2}^{h}}-1=2l-1\to l=\left( n+1 \right)/2$$. It also means that $$n = 2l - 1$$. In terms of the tree height $$h $$, $$l = (2^{h+1}-1 + 1) / 2 = 2^h$$.
 * For any non-empty binary tree with $$l $$ leaf nodes and $$i_2  $$ nodes of degree 2 (internal nodes with two child nodes), $$l = i_2 + 1  $$. The proof is the following. For a perfect binary tree, the total number of nodes is $$n = 2^{h+1}-1 $$ (A perfect binary tree is a full binary tree.) and $$l = 2^h$$, so $$i = n - l = (2^{h+1}-1) - 2^h = 2^h - 1 = l - 1 \to l = i + 1  $$. To make a full binary tree from a perfect binary tree, a pair of two sibling nodes are removed one by one. This results in "two leaf nodes removed" and "one internal node removed" and "the removed internal node becoming a leaf node", so one leaf node and one internal node is removed per removing two sibling nodes. As a result, $$l = i + 1$$ also holds for a full binary tree. To make a binary tree with a leaf node without its sibling, a single leaf node is removed from a full binary tree, then "one leaf node removed" and "one internal nodes with two children removed" so $$l = i + 1$$ also holds. This relation now covers all non-empty binary trees.
 * With given $$n $$ nodes, the minimum possible tree height is $$h_{min} = \log _2 (n+1)-1  $$ with which the tree is a balanced full tree or perfect tree. With a given height $$h$$, the number of nodes can't exceed the $$2^{h+1}-1 $$ as the number of nodes in a perfect tree. Thus $$n \leq 2^{h + 1} - 1 \to h \geq \log _2 (n + 1) - 1$$.
 * A binary Tree with $$l$$ leaves has at least the height $$h_m = \log _ 2 (l)$$. With a given height $$h$$, the number of leaves at that height can't exceed $$2^h$$ as the number of leaves at the height in a perfect tree. Thus $$l \leq 2^h \to h \geq \log _ 2 (l)$$.
 * In a non-empty binary tree, if $$n$$ is the total number of nodes and $$e$$ is the total number of edges, then $$e = n - 1$$. This is obvious because each node requires one edge except for the root node.
 * The number of null links (i.e., absent children of the nodes) in a binary tree of n nodes is (n + 1).
 * The number of internal nodes in a complete binary tree of n nodes is $$\lfloor n/2\rfloor $$.

Combinatorics
In combinatorics, one considers the problem of counting the number of full binary trees of a given size. Here the trees have no values attached to their nodes (this would just multiply the number of possible trees by an easily determined factor), and trees are distinguished only by their structure; however, the left and right child of any node are distinguished (if they are different trees, then interchanging them will produce a tree distinct from the original one). The size of the tree is taken to be the number n of internal nodes (those with two children); the other nodes are leaf nodes and there are $n + 1$ of them. The number of such binary trees of size n is equal to the number of ways of fully parenthesizing a string of $n + 1$ symbols (representing leaves) separated by n binary operators (representing internal nodes), to determine the argument subexpressions of each operator. For instance for $n = 3$ one has to parenthesize a string like $X*X*X*X$, which is possible in five ways:
 * $$((X*X)*X)*X,\qquad (X*(X*X))*X,\qquad (X*X)*(X*X),\qquad X*((X*X)*X),\qquad X*(X*(X*X)).$$

The correspondence to binary trees should be obvious, and the addition of redundant parentheses (around an already parenthesized expression or around the full expression) is disallowed (or at least not counted as producing a new possibility).

There is a unique binary tree of size 0 (consisting of a single leaf), and any other binary tree is characterized by the pair of its left and right children; if these have sizes i and j respectively, the full tree has size $i + j + 1$. Therefore, the number $$C_n$$ of binary trees of size n has the following recursive description $$C_0=1$$, and $$\textstyle C_n=\sum_{i=0}^{n-1}C_iC_{n-1-i}$$ for any positive integer n. It follows that $$C_n$$ is the Catalan number of index n.

The above parenthesized strings should not be confused with the set of words of length 2n in the Dyck language, which consist only of parentheses in such a way that they are properly balanced. The number of such strings satisfies the same recursive description (each Dyck word of length 2n is determined by the Dyck subword enclosed by the initial '(' and its matching ')' together with the Dyck subword remaining after that closing parenthesis, whose lengths 2i and 2j satisfy $i + j + 1 = n$); this number is therefore also the Catalan number $$C_n$$. So there are also five Dyck words of length 6:

These Dyck words do not correspond to binary trees in the same way. Instead, they are related by the following recursively defined bijection: the Dyck word equal to the empty string corresponds to the binary tree of size 0 with only one leaf. Any other Dyck word can be written as ($$w_1$$)$$w_2$$, where $$w_1$$,$$w_2$$ are themselves (possibly empty) Dyck words and where the two written parentheses are matched. The bijection is then defined by letting the words $$w_1$$ and $$w_2$$ correspond to the binary trees that are the left and right children of the root.

A bijective correspondence can also be defined as follows: enclose the Dyck word in an extra pair of parentheses, so that the result can be interpreted as a Lisp list expression (with the empty list as only occurring atom); then the dotted-pair expression for that proper list is a fully parenthesized expression (with NIL as symbol and '.' as operator) describing the corresponding binary tree (which is, in fact, the internal representation of the proper list).

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a free magma on a singleton set.

Methods for storing binary trees
Binary trees can be constructed from programming language primitives in several ways.

Nodes and references
In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special sentinel node.

This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative is threaded binary tree.

In languages with tagged unions such as ML, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. For example, the following line of code in OCaml (an ML dialect) defines a binary tree that stores a character in each node.

Arrays
Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices $$2i + 1$$ (for the left child) and $$2i +2$$ (for the right), while its parent (if any) is found at index $$\left \lfloor \frac{i-1}{2} \right \rfloor$$ (assuming the root has index zero). Alternatively, with a 1-indexed array, the implementation is simplified with children found at $$2i$$ and $$2i+1$$, and parent found at $$\lfloor i/2 \rfloor$$.

This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. It is often used for binary heaps.

Succinct encodings
A succinct data structure is one which occupies close to minimum possible space, as established by information theoretical lower bounds. The number of different binary trees on $$n$$ nodes is $$\mathrm{C}_{n}$$, the $$n$$th Catalan number (assuming we view trees with identical structure as identical). For large $$n$$, this is about $$4^{n}$$; thus we need at least about $$\log_{2}4^{n} = 2n$$ bits to encode it. A succinct binary tree therefore would occupy $$2n+o(n)$$ bits.

One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf. If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this:

function EncodeSuccinct(node n, bitstring structure, array data) { if n = nil then append 0 to structure; else append 1 to structure; append n.data to data; EncodeSuccinct(n.left, structure, data); EncodeSuccinct(n.right, structure, data); }

The string structure has only $$2n + 1$$ bits in the end, where $$n$$ is the number of (internal) nodes; we don't even have to store its length. To show that no information is lost, we can convert the output back to the original tree like this:

function DecodeSuccinct(bitstring structure, array data) { remove first bit of structure and put it in b if b = 1 then create a new node n remove first element of data and put it in n.data n.left = DecodeSuccinct(structure, data) n.right = DecodeSuccinct(structure, data) return n    else return nil }

More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form.

Encoding ordered trees as binary trees
There is a natural one-to-one correspondence between ordered trees and binary trees. It allows any ordered tree to be uniquely represented as a binary tree, and vice versa:

Let T be a node of an ordered tree, and let B denote T's image in the corresponding binary tree. Then B's left child represents T's first child, while the B's right child represents T's next sibling.

For example, the ordered tree on the left and the binary tree on the right correspond:

In the pictured binary tree, the black, left, edges represent first child, while the blue, right, edges represent next sibling.

This representation is called a left-child right-sibling binary tree.

Common operations
There are a variety of different operations that can be performed on binary trees. Some are mutator operations, while others simply return useful information about the tree.

Insertion
Nodes can be inserted into binary trees in between two other nodes or added after a leaf node. In binary trees, a node that is inserted is specified as to whose child it will be.

Leaf nodes
To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent.

Internal nodes
Insertion on internal nodes is slightly more complex than on leaf nodes. Say that the internal node is node A and that node B is the child of A. (If the insertion is to insert a right child, then B is the right child of A, and similarly with a left child insertion.) A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.

Deletion
Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.

Node with zero or one children
Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

Node with two children
In a binary tree, a node with two children cannot be deleted unambiguously. However, in certain binary trees (including binary search trees) these nodes can be deleted, though with a rearrangement of the tree structure.

Traversal
Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root. Below are the brief descriptions of above mentioned traversals.

Pre-order
In pre-order, we always visit the current node; next, we recursively traverse the current node's left subtree, and then we recursively traverse the current node's right subtree. The pre-order traversal is a topologically sorted one, because a parent node is processed before any of its child nodes is done.

In-order
In in-order, we always recursively traverse the current node's left subtree; next, we visit the current node, and lastly, we recursively traverse the current node's right subtree.

Post-order
In post-order, we always recursively traverse the current node's left subtree; next, we recursively traverse the current node's right subtree and then visit the current node. Post-order traversal can be useful to get postfix expression of a binary expression tree.

Depth-first order
In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles. Pre-order is a special case of this. See depth-first search for more information.

Breadth-first order
Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. See breadth-first search for more information. Also called a level-order traversal.

In a complete binary tree, a node's breadth-index (i − (2d − 1)) can be used as traversal instructions from the root. Reading bitwise from left to right, starting at bit d − 1, where d is the node's distance from the root (d = ⌊log$2$(i+1)⌋) and the node in question is not the root itself (d > 0). When the breadth-index is masked at bit d − 1, the bit values 0 and 1 mean to step either left or right, respectively. The process continues by successively checking the next bit to the right until there are no more. The rightmost bit indicates the final traversal from the desired node's parent to the node itself. There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer(s) to its sibling(s).

title: Binary tree


text:
Borel measure

In mathematics, specifically in measure theory, a Borel measure on a topological space is a measure that is defined on all open sets (and thus on all Borel sets). Some authors require additional restrictions on the measure, as described below.

Formal definition
Let $$X$$ be a locally compact Hausdorff space, and let $$\mathfrak{B}(X)$$ be the smallest σ-algebra that contains the open sets of $$X$$; this is known as the σ-algebra of Borel sets. A Borel measure is any measure $$\mu$$ defined on the σ-algebra of Borel sets. A few authors require in addition that $$\mu$$ is locally finite, meaning that $$\mu(C)<\infty$$ for every compact set $$C$$. If a Borel measure $$\mu$$ is both inner regular and outer regular, it is called a regular Borel measure. If $$\mu$$ is both inner regular, outer regular, and locally finite, it is called a Radon measure.

On the real line
The real line $$\mathbb R$$ with its usual topology is a locally compact Hausdorff space; hence we can define a Borel measure on it. In this case, $$\mathfrak{B}(\mathbb R)$$ is the smallest σ-algebra that contains the open intervals of $$\mathbb R$$. While there are many Borel measures μ, the choice of Borel measure that assigns $$\mu((a,b])=b-a$$ for every half-open interval $$(a,b]$$ is sometimes called "the" Borel measure on $$\mathbb R$$. This measure turns out to be the restriction to the Borel σ-algebra of the Lebesgue measure $$\lambda$$, which is a complete measure and is defined on the Lebesgue σ-algebra. The Lebesgue σ-algebra is actually the completion of the Borel σ-algebra, which means that it is the smallest σ-algebra that contains all the Borel sets and can be equipped with a complete measure. Also, the Borel measure and the Lebesgue measure coincide on the Borel sets (i.e., $$\lambda(E)=\mu(E)$$ for every Borel measurable set, where $$\mu$$ is the Borel measure described above). This idea extends to finite-dimensional spaces $$\mathbb R^n$$ (the Cramér–Wold theorem, below) but does not hold, in general, for infinite-dimensional spaces. Infinite-dimensional Lebesgue measures do not exist.

Product spaces
If X and Y are second-countable, Hausdorff topological spaces, then the set of Borel subsets $$B(X\times Y)$$ of their product coincides with the product of the sets $$B(X)\times B(Y)$$ of Borel subsets of X and Y. That is, the Borel functor
 * $$\mathbf{Bor}\colon\mathbf{Top}_\mathrm{2CHaus}\to\mathbf{Meas}$$

from the category of second-countable Hausdorff spaces to the category of measurable spaces preserves finite products.

Lebesgue–Stieltjes integral
The Lebesgue–Stieltjes integral is the ordinary Lebesgue integral with respect to a measure known as the Lebesgue–Stieltjes measure, which may be associated to any function of bounded variation on the real line. The Lebesgue–Stieltjes measure is a regular Borel measure, and conversely every regular Borel measure on the real line is of this kind.

Laplace transform
One can define the Laplace transform of a finite Borel measure μ on the real line by the Lebesgue integral

 * $$(\mathcal{L}\mu)(s) = \int_{[0,\infty)} e^{-st}\,d\mu(t).$$

An important special case is where μ is a probability measure or, even more specifically, the Dirac delta function. In operational calculus, the Laplace transform of a measure is often treated as though the measure came from a distribution function f. In that case, to avoid potential confusion, one often writes

 * $$(\mathcal{L}f)(s) = \int_{0^-}^\infty e^{-st}f(t)\,dt$$

where the lower limit of 0− is shorthand notation for

 * $$\lim_{\varepsilon\downarrow 0}\int_{-\varepsilon}^\infty.$$

This limit emphasizes that any point mass located at 0 is entirely captured by the Laplace transform. Although with the Lebesgue integral, it is not necessary to take such a limit, it does appear more naturally in connection with the Laplace–Stieltjes transform.

Moment problem
One can define the moments of a finite Borel measure μ on the real line by the integral

 * $$m_n = \int_a^b x^n\,d\mu(x).$$

For $$(a,b)=(-\infty,\infty),\;(0,\infty),\;(0,1)$$ these correspond to the Hamburger moment problem, the Stieltjes moment problem and the Hausdorff moment problem, respectively. The question or problem to be solved is, given a collection of such moments, is there a corresponding measure? For the Hausdorff moment problem, the corresponding measure is unique. For the other variants, in general, there are an infinite number of distinct measures that give the same moments.

Hausdorff dimension and Frostman's lemma
Given a Borel measure μ on a metric space X such that μ(X) > 0 and μ(B(x, r)) ≤ rs holds for some constant s > 0 and for every ball B(x, r) in X, then the Hausdorff dimension dimHaus(X) ≥ s. A partial converse is provided by the Frostman lemma:

Lemma: Let A be a Borel subset of Rn, and let s > 0. Then the following are equivalent:
 * Hs(A) > 0, where Hs denotes the s-dimensional Hausdorff measure.
 * There is an (unsigned) Borel measure μ satisfying μ(A) > 0, and such that
 * $$\mu(B(x,r))\le r^s$$
 * holds for all x ∈ Rn and r > 0.

Cramér–Wold theorem
The Cramér–Wold theorem in measure theory states that a Borel probability measure on $$\mathbb R^k$$ is uniquely determined by the totality of its one-dimensional projections. It is used as a method for proving joint convergence results. The theorem is named after Harald Cramér and Herman Ole Andreas Wold.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Borel measure


text:
Blackadder

Blackadder is a series of four period British sitcoms, plus several one-off instalments, which originally aired on BBC1 from 1983 to 1989. All television episodes starred Rowan Atkinson as the antihero Edmund Blackadder and Tony Robinson as Blackadder's dogsbody, Baldrick. Each series was set in a different historical period, with the two protagonists accompanied by different characters, though several reappear in one series or another, e.g., Melchett (Stephen Fry), Lord Percy Percy / Captain Darling (Tim McInnerny) and George (Hugh Laurie).

The first series, The Black Adder, was written by Richard Curtis and Rowan Atkinson, while subsequent series were written by Curtis and Ben Elton. The shows were produced by John Lloyd. In 2000, the fourth series, Blackadder Goes Forth, ranked at 16 in the 100 Greatest British Television Programmes, a list created by the British Film Institute. In a 2001 poll by Channel 4, Edmund Blackadder was ranked third on their list of the 100 Greatest TV Characters. In the 2004 TV poll to find Britain's Best Sitcom, Blackadder was voted the second-best British sitcom of all time, topped by Only Fools and Horses. It was also ranked as the 9th-best TV show of all time by Empire magazine. Rowan Atkinson said Blackadder is "the thing he found the least stressful" to do.

Premise
Each series is set in a different period of British history, beginning in 1485 and ending in 1917, and comprises six half-hour episodes. Blackadder follows the misfortunes of Edmund Blackadder (played by Atkinson). It is implied in each series that the Blackadder character is a descendant of the previous one; the end theme lyrics of series 2 episode "Head" specify that he is the great-grandson of the previous, although it is never specified how or when any of the Blackadders (who are usually bachelors) managed to father children. In series one, Edmund Blackadder is not particularly bright, and is much the intellectual inferior of his servant, Baldrick (played by Tony Robinson). However, in subsequent series, the positions are reversed: Blackadder is clever, shrewd, scheming and manipulative while Baldrick is extremely dim. Each incarnation of Blackadder and Baldrick is also saddled with tolerating the presence of a dimwitted aristocrat. In the first two series, this is Lord Percy Percy, played by Tim McInnerny. Hugh Laurie plays the role in the third and fourth series, as Prince George, Prince Regent, and Lieutenant George respectively, and by Stephen Fry as Lord Melchett.

The first series, made in 1983, was called The Black Adder and was set in the fictional reign of "Richard IV". The second series, Blackadder II (1986), was set during the reign of Elizabeth I. Blackadder the Third (1987) was set during the late 18th and early 19th centuries in the reign of George III, and Blackadder Goes Forth (1989) was set in 1917 in the trenches of the Great War.

Series 1: The Black Adder
The Black Adder, the first series of Blackadder, was written by Richard Curtis and Rowan Atkinson and produced by John Lloyd. It originally aired on BBC1 from 15 June 1983 to 20 July 1983, and was a joint production with the Australian Seven Network.

Set in 1485 at the end of the British Middle Ages, the series is written as an alternative history in which Richard III won the Battle of Bosworth Field only to be mistaken for someone else and murdered, and is succeeded by Richard IV (Brian Blessed), one of the Princes in the Tower. The series follows the exploits of Richard IV's unfavoured second son Edmund, the Duke of Edinburgh (who calls himself "The Black Adder") in his various attempts to increase his standing with his father and his eventual quest to overthrow him. Guest appearances in this series include Peter Cook as King Richard III, Russell Enoch as the Duke of Winchester, Miriam Margolyes as the Infanta Maria Escalosa of Spain (with Jim Broadbent as her interpreter), Frank Finlay as the Witchsmeller Pursuivant, Valentine Dyall as Lord Angus, Stephen Frost and Mark Arden as guards, and Rik Mayall as Mad Gerald.

Conceived while Atkinson and Curtis were working on Not the Nine O'Clock News, the series dealt comically with a number of aspects of medieval life in Britain: witchcraft, royal succession, European relations, the Crusades, and the conflict between the Church and the Crown. Along with the secret history, many historical events portrayed in the series were anachronistic (for example, Constantinople had already fallen to the Ottoman Empire in 1453, predating the events in the episode by 32 years); this dramatic license would continue in the subsequent Blackadders. The filming of the series was highly ambitious, with a large cast and much location shooting. The series also featured Shakespearean dialogue, often adapted for comic effect; the end credits featured the words "Additional Dialogue by William Shakespeare".

Series 2: Blackadder II
Blackadder II is set in England during the reign of Queen Elizabeth I (1558–1603), who is portrayed by Miranda Richardson. The principal character is Edmund, Lord Blackadder, the great-grandson of the original Black Adder. During the series, he regularly deals with the Queen, her obsequious Lord Chamberlain Lord Melchett (Stephen Fry; his rival for the Queen's affections), his friend Lord Percy Percy (played by Tim McInnerny) and the Queen's demented former nanny Nursie (Patsy Byrne). Guest appearances in the series include Tom Baker as Captain Redbeard Rum, Simon Jones as Sir Walter Raleigh, Ronald Lacey as the Bishop of Bath and Wells, and Miriam Margoyles as Blackadder's aunt, Lady Whiteadder. The series also features two appearances by Hugh Laurie (as Simon Partridge, a friend of Blackadder's, in the episode "Beer"; and as Prince Ludwig the Indestructible in the series' finale "Chains"), as well as the first appearance of Gabrielle Glaister as "Bob", and of Rik Mayall as Lord Flashheart.

Following the BBC's request for improvements (and a severe budget reduction), several changes were made. The second series was the first to establish the familiar Blackadder character: cunning, shrewd and witty, in sharp contrast to the first series' bumbling Prince Edmund. To reduce the cost of production, it was shot with virtually no outdoor scenes (the first series was shot largely on location) and several frequently used indoor sets, such as the Queen's throne room and Blackadder's front room.

A quote from this series ranked number three in a list of the top 25 television "putdowns" of the last 40 years by the Radio Times magazine: "The eyes are open, the mouth moves, but Mr. Brain has long since departed, hasn't he, Percy?"

Series 3: Blackadder the Third
Blackadder the Third is set in the late 18th and early 19th centuries, a period known as the Regency. In the series, Edmund Blackadder Esquire is the butler to the Prince Regent, the Prince of Wales. (The prince is played by Hugh Laurie as a complete fop and idiot.) Despite Edmund's respected intelligence and abilities, he has no personal fortune to speak of, apart from his frequently fluctuating wage packet (as well, it seems, from stealing and selling off the Prince's socks) from the Prince: "If I'm running short of cash, all I have to do is go upstairs and ask Prince Fathead for a rise." The episode titles were puns on Jane Austen novels.

As well as Rowan Atkinson and Tony Robinson in their usual roles, this series starred Hugh Laurie as the Prince Regent and Helen Atkinson-Wood as Mrs. Miggins. The series features Dr. Samuel Johnson (Robbie Coltrane); William Pitt the Younger (Simon Osborne); the French Revolution (with Chris Barrie, Tim McInnerny as the Scarlet Pimpernel, and Nigel Planer); hammy theatrical actors (Kenneth Connor and Hugh Paddick); a squirrel-hating cross-dressing highwayman (Miranda Richardson); and a duel with the Duke of Wellington (Stephen Fry).

Series 4: Blackadder Goes Forth
This series is set in 1917, on the Western Front in the trenches of the First World War. Another "big push" is planned, and Captain Blackadder's one goal is to avoid being killed, but his schemes always land him back in the trenches. Blackadder is joined by his batman Private S. Baldrick (Tony Robinson) and idealistic Edwardian twit Lieutenant George (Hugh Laurie). General Melchett (Stephen Fry) rallies his troops from a French château 35 mi from the front, where he is aided and abetted by his assistant, Captain Kevin Darling (Tim McInnerny), pencil-pusher supreme and Blackadder's nemesis, whose name is played on for maximum comedic value. Guest appearances in this series include Stephen Frost as the leader of a firing squad detail, Miranda Richardson as Nurse Mary Fletcher-Brown, two further appearances of Gabrielle Glaister as "Bob" (in this series, a young woman who pretended to be a boy in order to join the army), Rik Mayall appearing as Royal Flying Corps Squadron Commander The Lord Flasheart, Adrian Edmondson as Baron Manfred von Richthofen (aka "The Red Baron"), and Geoffrey Palmer as Field Marshal Douglas Haig.

The series' tone is somewhat darker than the other Blackadders; it details the privations of trench warfare as well as the incompetence and life-wasting strategies of the top brass. For example, Baldrick is reduced to cooking rats and making coffee from mud, while General Melchett hatches a plan for the troops to walk very slowly toward the German lines, because "it'll be the last thing Fritz will expect."

The final episode, "Goodbyeee", is known for being extraordinarily poignant for a comedy – especially the final scene, which sees the main characters (Blackadder, Baldrick, George, and Darling) finally going "over the top" and charging off into the fog and smoke of no man's land, presumably to die. In a list of the 100 Greatest British Television Programmes, drawn up by the British Film Institute in 2000 and voted for by industry professionals, Blackadder Goes Forth was placed 16th.

Pilot episode
The Blackadder pilot was shot but never broadcast on TV in the UK (although some scenes were shown in the 25th anniversary special Blackadder Rides Again). One notable difference in the pilot, as in many pilots, is the casting. Baldrick is played not by Tony Robinson, but by Philip Fox. Another significant difference is that the character of Prince Edmund presented in the pilot is much closer to the intelligent, conniving Blackadder of the later series than the snivelling, weak buffoon of the original. Set in the year 1582, the script of the pilot is roughly the same as the episode "Born to Be King", albeit with some different jokes, with some lines appearing in other episodes of the series.

UKTV Gold broadcast the pilot on 15 June 2023, as part of an 80-minute special hosted by Sir Tony Robinson and featuring interviews with Ben Elton and Richard Curtis.

Blackadder: The Cavalier Years
This special, set in the English Civil War, was shown as part of Comic Relief's Red Nose Day on Friday 5 February 1988. The 15-minute episode is set in November 1648, during the last days of the Civil War. Sir Edmund Blackadder and his servant, Baldrick, are the last two men loyal to the defeated King Charles I of England (played by Stephen Fry), portrayed as a soft-spoken, ineffective, naive character, with the voice and mannerisms of Charles I's namesake, the then Prince of Wales (now Charles III). However, due to a misunderstanding between Oliver Cromwell (guest-star Warren Clarke) and Baldrick, the King is arrested and sent to the Tower of London. The rest of the episode revolves around Blackadder's attempts to save the King as well as improve his own standing.

Blackadder's Christmas Carol
The second special was broadcast on Friday 23 December 1988. In a twist on Charles Dickens' A Christmas Carol, Ebenezer Blackadder is the "kindest and loveliest" man in England. The Spirit of Christmas shows Blackadder the contrary antics of his ancestors and descendants, and reluctantly informs him that if he turns evil his descendants will enjoy power and fortune, while if he remains the same a future Blackadder will live shamefully subjugated to a future incompetent Baldrick. This remarkable encounter causes him to proclaim, "Bad guys have all the fun", and adopt the personality with which viewers are more familiar.

Blackadder: Back & Forth
Blackadder: Back & Forth was originally shown in the Millennium Dome in 2000, followed by a screening on Sky One in the same year (and later on BBC1). It is set on the turn of the millennium, and features Lord Blackadder placing a bet with his friends – modern versions of Queenie (Miranda Richardson), Melchett (Stephen Fry), George (Hugh Laurie) and Darling (Tim McInnerny) – that he has built a working time machine. While this is intended as a clever con trick, the machine surprisingly works, sending Blackadder and Baldrick back to the Cretaceous period, where they manage to cause the extinction of the dinosaurs through the use of Baldrick's best-worst-and-only pair of underpants as a weapon against a hungry T. Rex. Finding that Baldrick has forgotten to write dates on the machine's dials, the rest of the film follows their attempts to find their way back to 1999, often creating huge historical anomalies in the process that must be corrected before the end. The film includes cameo appearances from Kate Moss and Colin Firth.

The Big Night In
Broadcast in 2020 as part of Children in Need and Comic Relief's joint special The Big Night In during the COVID-19 pandemic, Fry resumed the role of Lord Melchett (an intellectually-brilliant version), Head of the Royal Household, under lockdown at Melchett Manor, to help Prince William deal with educating his children via Zoom and discussing Tiger King, before they both step outside to clap for the National Health Service. Melchett is said to be isolating with Lord Blackadder, both grandsons to their First World War counterparts.

Live stage performances
In 1998, as part of Prince Charles' 50th Birthday Gala televised on ITV, Atkinson returned to the Cavalier incarnation of Blackadder reading aloud a letter to the Privy Council of King Charles I. He colourfully refuses their invitation to stage a royal gala, calling such occasions "very, very, very dull" and asserting that there was "more musical talent on display when my servant Baldrick breaks wind."

In 2000, on the BBC's annual Royal Variety Performance, Atkinson portrayed Blackadder as a present-day officer in "Her Majesty's Royal Regiment of Shirkers" and delivered a monologue titled "Blackadder: The Army Years", proposing that Britain regain her former greatness by invading (or at least buying) France.

In 2012, as part of the Prince's Trust charity show We Are Most Amused, Atkinson and Robinson reprised their roles as Blackadder and Baldrick in a comedy sketch featuring Miranda Hart as leader of a government inquiry into the recent banking crisis. Blackadder, chief executive of a fictional British bank, appearing with Baldrick as his gardener, convinces the panel to publicly blame the entire crisis on Baldrick, to the latter's consternation.

Red Nose Day 2023
Baldrick (Tony Robinson) returned in 2023 for a Red Nose Day sketch for the BBC. There was no involvement of Rowan Atkinson or a subsequent reboot, amid speculation.

Series development
Rowan Atkinson and Richard Curtis developed the idea for the sitcom while working on Not the Nine O'Clock News. Eager to avoid comparisons to the critically acclaimed Fawlty Towers, they proposed the idea of a historical sitcom. An unaired pilot episode was made in 1982, and a six-episode series was commissioned. The budget for the series was considerable, with much location shooting particularly at Alnwick Castle in Northumberland and the surrounding countryside in February 1983. The series also used large casts of extras, horses and expensive medieval-style costumes. Atkinson has said about the making of the first series:

"The first series was odd, it was very extravagant. It cost a million pounds for the six programmes ... [which] was a lot of money to spend ... It looked great, but it wasn't as consistently funny as we would have liked."

Due to the high cost of the first series, the then-controller of programming of BBC1, Michael Grade, was reluctant to sign off a second series without major improvements to the show and drastic cost-cutting, leaving a gap of three years between the two series. Atkinson did not wish to continue writing for the second series.

A chance meeting between Richard Curtis and comedian Ben Elton led to the decision to collaborate on a new series of Blackadder. Recognising the main faults of the first series, Curtis and Elton agreed that Blackadder II would be a studio-only production (along with the inclusion of a live audience during recording, instead of showing the episodes to an audience after taping). Besides adding a greater comedy focus, Elton suggested a major change in character emphasis: Baldrick would become the stupid sidekick, while Edmund Blackadder evolved into a cunning sycophant. This led to the familiar set-up that was maintained in the following series.

Only in the Back & Forth millennium special was the shooting once again on location, because this was a production with a budget estimated at £3 million, and was a joint venture between Tiger Aspect, Sky Television, the New Millennium Experience Company and the BBC, rather than the BBC alone.

Casting
Each series tended to feature the same set of regular actors in different period settings, although throughout the four series and specials, only Blackadder and Baldrick were constant characters. Several regular cast members recurred as characters with similar names, implying, like Blackadder, that they were descendants.

Recurring cast
Various actors have appeared in more than one of the Blackadder series and/or specials. These are:

Main cast

 * Rowan Atkinson as Edmund Blackadder, the series' protagonist.
 * Tony Robinson as S. Baldrick, his servant.
 * Stephen Fry as Melchett in two series, first as Lord Melchett, the sycophantic adviser to Queen Elizabeth I in series two and secondly as General Melchett, a blustering buffoon and presumed descendant in series four. Fry also appeared as Arthur Wellesley, The Duke of Wellington in series three and as various characters in Blackadder Back & Forth.
 * Tim McInnerny as Lord Percy Percy, Blackadder's dimwitted sidekick in series one and two before a change of character to antagonistic rival Captain Kevin Darling in series four. He also appeared as The Scarlet Pimpernel (alias Lord Topper and Le Comte de Frou Frou) for one episode in the third series, and reprised his role as Darling in Blackadder: Back & Forth.
 * Hugh Laurie played George in series three and four, first as The Prince Regent, and later Lieutenant George in series four. Laurie also appeared twice in series two; firstly as Simon "Farters Parters" Partridge or "Mr. Ostrich" in the episode, "Beer", and then as Prince Ludwig the Indestructible in "Chains", the final instalment episode of Blackadder II. He reprised his role as George in Blackadder: Back & Forth.
 * Miranda Richardson was only a regular cast member for series two, in which she played Queen Elizabeth I, reprising the role in Blackadder's Christmas Carol and Back & Forth. However, she also played significant one-off roles as Amy Hardwood (a.k.a. The Shadow) in "Amy and Amiability" in the third series and Mary Fletcher-Brown, a dutiful nurse in "General Hospital" from the fourth. She reappeared as Queenie and additional characters in Christmas Carol and Back and Forth.

Non-recurring cast

 * Brian Blessed, Elspet Gray and Robert East appeared in all six episodes of the first series as the Black Adder's father, mother and brother respectively. Gray had also appeared in the non-broadcast pilot.
 * Patsy Byrne played Nursie in all six episodes of Blackadder II, but never featured in either of the subsequent series, either as a regular character or one-off. She briefly reprised the character in Blackadder: Back & Forth and Blackadder's Christmas Carol.
 * Helen Atkinson-Wood played the role of Mrs. Miggins in all six episodes of Blackadder the Third, but did not appear again in the series, although the character was mentioned several times in Blackadder II and in the final episode of Blackadder Goes Forth.

Guest cast
Ben Elton's arrival after the first series heralded the more frequent recruitment of comic actors from the alternative comedy era for guest appearances, including Robbie Coltrane, Rik Mayall (who had appeared in the final episode of the first series as "Mad Gerald"), Adrian Edmondson, Nigel Planer, Mark Arden, Stephen Frost, Chris Barrie and Jeremy Hardy. Elton himself played an anarchist in Blackadder the Third.

Gabrielle Glaister played Bob, an attractive girl who poses as a man, in both series 2 and 4. Rik Mayall plays Lord Flashheart, a vulgar friend in his first appearance and then a successful rival of Blackadder in later episodes of series 2 and 4. He also played a decidedly Flashheart-like Robin Hood in Back & Forth. Lee Cornes also appeared in an episode of all three Curtis-Elton series. He appeared as a guard in the episode "Chains" of Blackadder II; as the poet Shelley in the episode "Ink and Incapability' of Blackadder the Third; and as firing squad soldier Private Fraser in the episode "Corporal Punishment" of Blackadder Goes Forth.

More established actors, some at the veteran stage of their careers, were also recruited for roles. These included Peter Cook, John Grillo, Simon Jones, Tom Baker, Jim Broadbent, Hugh Paddick, Frank Finlay, Kenneth Connor, Bill Wallis, Ronald Lacey, Roger Blake, Denis Lill, Warren Clarke and Geoffrey Palmer, who played Field Marshal Sir Douglas Haig in "Goodbyeee", the final episode of Blackadder Goes Forth. Miriam Margolyes played three different guest roles: The Spanish Infanta in The Queen of Spain's Beard, Lady Whiteadder in Beer, and Queen Victoria in Blackadder's Christmas Carol.

Unusually for a sitcom based loosely on factual events and in the historical past, a man was recruited for one episode essentially to play himself. Political commentator Vincent Hanna played a character billed as "his own great-great-great grandfather" in the episode "Dish and Dishonesty" of Blackadder the Third. Hanna was asked to take part because the scene was of a by-election in which Baldrick was a candidate and, in the style of modern television, Hanna gave a long-running "live" commentary of events at the count (and interviewed candidates and election agents) to a crowd through the town hall window.

Theme tune
Howard Goodall's theme tune has the same melody throughout all the series, but is played in roughly the style of the period in which it is set. It is performed mostly with trumpets and timpani in The Black Adder, the fanfares used suggesting typical medieval court fanfares; with a combination of recorder, string quartet and electric guitar in Blackadder II (the end theme, with different lyrics each time reflecting on the episode's events, was sung by a countertenor); on oboe, cello and harpsichord (in the style of a minuet) for Blackadder the Third; by The Band of the 3rd Battalion, Royal Anglian Regiment in Blackadder Goes Forth; sung by carol singers in Blackadder's Christmas Carol; and by an orchestra in Blackadder: The Cavalier Years and Blackadder: Back & Forth.

Awards
In 2000, the fourth series, Blackadder Goes Forth, ranked at 16 in the "100 Greatest British Television Programmes", a list created by the British Film Institute. In 2004, a BBC TV poll for "Britain's Best Sitcom", Blackadder was voted the second best British sitcom of all time, topped by Only Fools and Horses. It was also ranked as the 20th Best TV Show of All Time by Empire magazine.

Future
Despite regular statements denying any plans for a fifth series, cast members are regularly asked about the possibility of a new series.

In January 2005, Tony Robinson told ITV's This Morning that Rowan Atkinson was more keen than he has been in the past to do a fifth series, set in the 1960s (centred on a rock band called the "Black Adder Five", with Baldrick – a.k.a. 'Bald Rick' – as the drummer). In the documentary Blackadder Rides Again, Robinson stated that the series would present Blackadder as the bastard son of Queen Elizabeth II and running a Beatles-like rock band. Rowan Atkinson, Tony Robinson, Hugh Laurie, Stephen Fry, Tim McInnerny and Miranda Richardson would have reprised their roles, and reportedly, Brian Blessed, Elspet Gray and Robert East would have returned from the first series to play Blackadder's biological family. Robinson in a stage performance 1 June 2007, again mentioned this idea, but in the context of a movie.

One idea mentioned by Curtis was that it was Baldrick who had accidentally assassinated John F. Kennedy. However, aside from a brief mention in June 2005, there have been no further announcements from the BBC that a new series is being planned. Furthermore, in November 2005, Rowan Atkinson told BBC Breakfast that, although he would very much like to do a new series set in Colditz or another prisoner-of-war camp during World War II, something which both he and Stephen Fry reiterated at the end of Blackadder Rides Again, the chances of it happening are extremely slim.

There were a couple of ideas that had previously floated for the fifth series. Batadder was intended to be a parody of Batman with Baldrick as the counterpart of Robin (suggested by John Lloyd). This idea eventually came to surface as part of the Comic Relief sketch "Spider-Plant Man" in 2005, with Atkinson as the title hero, Robinson as Robin, Jim Broadbent as Batman and Rachel Stevens as Mary Jane. Star Adder was to be set in space in the future (suggested by Atkinson), though this too was touched upon in Blackadder's Christmas Carol.

On 10 April 2007, Hello! reported that Atkinson was moving forward with his ideas for a fifth series. He said, "I like the idea of him being a prisoner of war in Colditz. That would have the right level of authority and hierarchy which is apparent in all the Blackadders."

A post on BlackAdderHall.com by Ben Elton in early 2007 said that Blackadder would return in some form, whether it be a TV series or film. Elton has since not given any more information on the putative Blackadder 5.

During an interview in August 2007 about his film Mr. Bean's Holiday, Atkinson was asked about the possibility of a further Blackadder series, to which the simple reply "No, no chance" was given:

"There was a plan for a film set in the Russian revolution, a very interesting one called The Red Adder. He would have been a lieutenant in the Secret Police. Then the revolution happened and at the end he is in the same office doing the same job but just the colours on his uniform have changed. It was quite a sweet idea and we got quite a long way with it but in the end it died a death."

Stephen Fry has expressed the view that, since the series went out on such a good "high", a film might not be a good idea.

During his June 2007 stage performance, chronicled on the Tony Robinson's Cunning Night Out DVD, Robinson states that, after filming the Back & Forth special, the general idea was to reunite for another special in 2010. Robinson jokingly remarked that Hugh Laurie's success on House may make that difficult.

On 28 November 2012, Rowan Atkinson reprised the role at the "We are most amused" comedy gala for the Prince's Trust at the Royal Albert Hall. He was joined by Tony Robinson as Baldrick. The sketch involved Blackadder as CEO of Melchett, Melchett and Darling bank facing an enquiry over the banking crisis.

In August 2015, Tony Robinson said in an interview "I do think a new series of Blackadder is on the cards. I have spoken to virtually all the cast about this now. The only problem is Hugh [Laurie]'s fee. He's a huge star now." However, in October 2018, Richard Curtis "dashed hopes" that the show would return for a fifth series.

In December 2020, Rowan Atkinson told the Radio Times:

"I don't actually like the process of making anything – with the possible exception of Blackadder. Because the responsibility for making that series funny was on many shoulders, not just mine. Blackadder represented the creative energy we all had in the '80s. To try to replicate that 30 years on wouldn't be easy."

Home media
All series and many of the specials are available on VHS tapes, DVD & BluRay. Many are also available on BBC audio cassette. As of 2008, a "Best of BBC" edition box set is available containing all four major series together with Blackadder's Christmas Carol and Back & Forth. All four series and the Christmas special are also available for download on iTunes.

VHS releases
On 5 February 1990, BBC Enterprises Ltd released the first series on two single VHS tapes.

On 2 October 1989, BBC Enterprises Ltd released the second series on two single VHS tapes.

On 6 February 1989, BBC Enterprises Ltd released the third series on two single VHS tapes.

On 10 September 1990, BBC Enterprises Ltd released the fourth and final series on two single VHS tapes.

On 7 September 1992, all eight single Blackadder video releases were re-released as four "complete" double VHS releases. The four entire series videos were re-released as single VHS tape releases on 2 October 1995.

On 5 January 1998, five episodes of the first two series were released on a 15-rated VHS tape compilation by BBC Worldwide Ltd.

On 4 November 1991, Blackadder's Christmas Carol was released on a single VHS tape release rated PG (Cat. No. BBCV 4646).

LP box set
On 19 October 2022 there was an announcement that there will be a LP box set release and collects the Blackadder soundtracks on vinyl for the first time. The deluxe 12-disc LP collection with the title Blackadder's Historical Record was pressed on gold-couloured 140g vinyl, and released on 10 February 2023 by Demon Records. It also includes a frameable print of Baldrick, each hand signed by Sir Tony Robinson himself and a comprehensive full-colour booklet detailing the comedy series, the "leather-look rigid box"

Stamps
Royal Mail issued a set of special stamps celebrating Blackadder on 17 May 2023.

Literature

 * Richard Curtis, Ben Elton, and Rowan Atkinson, Blackadder: The Whole Damn Dynasty 1485–1917 (Michael Joseph, 1998). ISBN 0-7181-4372-8. Being the – almost – complete scripts of the four regular series.
 * Chris Howarth, and Steve Lyons, Cunning: The Blackadder Programme Guide (Virgin Publishing, 2002). ISBN 0-7535-0447-2. A cheap unofficial episode guide.
 * Richard Curtis and Ben Elton, Blackadder: Back & Forth (Penguin Books, 2000). ISBN 0-14-029135-0. A script book with copious photographs from the most recent outing, and additional material from Kevin Cecil & Andy Riley.
 * J.F. Roberts, The True History of the Black Adder: The Unadulterated Tale of the Creation of a Comedy Legend (Preface publishing, 2012). ISBN 978-1-84809-346-1. A 420-page officially endorsed full history of the Blackadder episodes and characters, as well as its birth, its writers and actors, and all the specials – plus Curtis' script for unproduced Christmas special 'Blackadder In Bethlehem'.

title: Blackadder


text:
Boii

The Boii (Latin plural, singular Boius; Βόιοι) were a Celtic tribe of the later Iron Age, attested at various times in Cisalpine Gaul (present-day Northern Italy), Pannonia (present-day Austria and Hungary), present-day Bavaria, in and around present-day Bohemia (after whom the region is named in most languages; comprising the bulk of today's Czech Republic), parts of present-day Slovakia and Poland, and Gallia Narbonensis (located in modern Languedoc and Provence).

In addition, the archaeological evidence indicates that in the 2nd century BC Celts expanded from Bohemia through the Kłodzko Valley into Silesia, now part of Poland and the Czech Republic.

They first appear in history in connection with the Gallic invasion of northern Italy, 390 BC, when they made the Etruscan city of Felsina their new capital, Bononia (Bologna).

After a series of wars, they were decisively beaten by the Romans in the Battle of Mutina (193 BC) and their territory became part of the Roman province of Cisalpine Gaul. According to Strabo, writing two centuries after the events, rather than being destroyed by the Romans like their Celtic neighbours,"The Boii were merely driven out of the regions they occupied; and after migrating to the regions round about the Ister, lived with the Taurisci, and carried on war against the Daci until they perished, tribe and all—and thus they left their country, which was a part of Illyria, to their neighbours as a pasture-ground for sheep."

Around 60 BC, a group of Boii joined the Helvetiis' ill-fated attempt to conquer land in western Gaul and were defeated by Julius Caesar, along with their allies, in the Battle of Bibracte.

Caesar settled the remnants of that group in Gorgobina, from where they sent 2,000 warriors to Vercingetorix's aid at the Battle of Alesia six years later. The eastern Boii on the Danube were incorporated into the Roman Empire in 8 AD.

Etymology and name
From all the different names of the same Celtic people in literature and inscriptions, it is possible to abstract a Continental Celtic segment, boio-.

There are two major derivations of this segment, both presupposing that it belongs to the family of Indo-European languages: from 'cow' and from 'warrior.' The Boii would thus be either 'the herding people' or 'the warrior people'.

The 'cow' derivation depends most immediately on the Old Irish legal term for 'outsider': ambue, from Proto-Celtic *ambouios (<*an-bouios), 'not a cattle owner'.

In a reference to the first known historical Boii, Polybius relates that their wealth consisted of cattle and gold, that they depended on agriculture and war, and that a man's status depended on the number of associates and assistants he had. The latter were presumably the *ambouii, as opposed to the man of status, who was *bouios, a cattle owner, and the *bouii were originally a class, 'the cattle owners'. The 'warrior' derivation was adopted by the linguist Julius Pokorny, who presented it as being from Indo-European *bhei(ə)-, *bhī-, 'hit'; however, not finding any Celtic names close to it (except for the Boii), he adduces examples somewhat more widely from originals further back in time: phohiio-s-, a Venetic personal name; Boioi, an Illyrian tribe; Boiōtoi, a Greek tribal name (the Boeotians); and a few others.

The same wider connections can be hypothesized for the 'cow' derivation: the Boeotians have been known for well over a century as a people of kine, which might have been parallel to the meaning of Italy as 'land of calves'. Indo-European reconstructions can be made using 'cow' as a basis, such as ; the root may itself be an imitation of the sound a cow makes.

Contemporary derived words include Boiorix ('king of the Boii', one of the chieftains of the Cimbri) and Boiodurum ('gate/fort of the Boii', modern Passau) in Germany. Their memory also survives in the modern regional names of Bohemia (Boiohaemum), a mixed-language form from boio- and Proto-Germanic *haimaz, 'home': 'home of the Boii', and Bayern, Bavaria, which is derived from the Germanic Baiovarii tribe (Germanic *baja-warjaz: the first component is most plausibly explained as a Germanic version of Boii; the second part is a common formational morpheme of Germanic tribal names, meaning 'dwellers', as in Old English -ware); this combination 'Boii-dwellers' may have meant 'those who dwell where the Boii formerly dwelt'.

Settlement in north Italy
According to the ancient authors, the Boii arrived in northern Italy by crossing the Alps. While of the other tribes who had come to Italy along with the Boii, the Senones, Lingones and Cenomani are also attested in Gaul at the time of the Roman conquest. It remains therefore unclear where exactly the Central Europe origins of the Boii lay, if somewhere in Gaul, Southern Germany or in Bohemia.

Polybius relates that the Celts were close neighbors of the Etruscan civilization and "cast covetous eyes on their beautiful country".

Invading the Po Valley with a large army, they drove out the Etruscans and resettled it, the Boii taking the right bank in the center of the valley. Strabo confirms that the Boii emigrated from their lands across the Alps and were one of the largest tribes of the Celts. The Boii occupied the old Etruscan settlement of Felsina, which they named Bononia (modern Bologna). Polybius describes the Celtic way of life in Cisalpine Gaul as follows: "They lived in unwalled villages, without any superfluous furniture; for as they slept on beds of leaves and fed on meat and were exclusively occupied with war and agriculture, their lives were very simple, and they had no knowledge whatever of any art or science.

Their possessions consisted of cattle and gold, because these were the only things they could carry about with them everywhere according to circumstances and shift where they chose. They treated comradeship as of the greatest importance, those among them being the most feared and most powerful who were thought to have the largest number of attendants and associates."

The archaeological evidence from Bologna and its vicinity contradicts the testimony of Polybius and Livy on some points, who say the Boii expelled the Etruscans and perhaps some were forced to leave.

It indicates the Boii neither destroyed nor depopulated Felsinum, but simply moved in and became part of the population by intermarriage.

The cemeteries of the period in Bologna contain La Tène weapons and other artifacts, as well as Etruscan items such as bronze mirrors. At Monte Bibele not far away one grave contained La Tène weapons and a pot with an Etruscan female name scratched on it.

War against Rome
In the second half of the 3rd century BC, the Boii allied with the other Cisalpine Gauls and the Etruscans against Rome. They also fought alongside Hannibal, killing the Roman general Lucius Postumius Albinus in 216 BC, whose skull was then turned into a sacrificial bowl.

A short time earlier, they had been defeated at the Battle of Telamon in 225 BC, and were again at Placentia in 194 BC (modern Piacenza) and Mutina in 193 BC (modern Modena). Publius Cornelius Scipio Nasica completed the Roman conquest of the Boii in 191 BC, celebrating a triumph for it. After their losses, according to Strabo, a large portion of the Boii left Italy.

Boii on the Danube
Contrary to the interpretation of the classical writers, the Pannonian Boii attested in later sources are not simply the remnants of those who had fled from Italy, but rather another division of the tribe, which had settled there much earlier.

The burial rites of the Italian Boii show many similarities with contemporary Bohemia, such as inhumation, which was uncommon with the other Cisalpine Gauls, or the absence of the typically western Celtic torcs.

This makes it much more likely that the Cisalpine Boii had actually originated from Bohemia rather than the other way round.

Having migrated to Italy from north of the Alps, some of the defeated Celts simply moved back to their kinsfolk.

The Pannonian Boii are mentioned again in the late 2nd century BC when they repelled the Cimbri and Teutones (Strabo VII, 2, 2). Later on, they attacked the city of Noreia (in modern Austria) shortly before a group of Boii (32,000 according to Julius Caesar) joined the Helvetii in their attempt to settle in western Gaul.

After the Helvetian defeat at Bibracte, the influential Aedui tribe allowed the Boii survivors to settle on their territory, where they occupied the oppidum of Gorgobina. Although attacked by Vercingetorix during one phase of the war, they supported him with two thousand troops at the battle of Alesia (Caesar, Commentarii de Bello Gallico, VII, 75).

Again, other parts of the Boii had remained closer to their traditional home, and settled in the Slovak and Hungarian lowlands by the Danube and the Mura, with a centre at Bratislava.

Dacian Conquest
Around 60 BC, they clashed with the rising power of the Dacians under their king Burebista and were defeated. The Dacians, under the leadership of Burebista, likely used a combination of military force and political strategies to conquer the Boii and compel some of them to migrate. Burebista's aggressive expansionist policies may have included military campaigns aimed at weakening the Boii and forcing them to surrender or flee. Additionally, Burebista may have employed diplomatic tactics to sow discord among the Boii to further pressure them.

Once the Boii were defeated or weakened, the Dacians would have annexed their territory, incorporating it into their expanding kingdom. The migration of the Boii through Europe may have been a consequence of their defeat and the Dacian occupation of their lands, as they sought new territories and opportunities elsewhere. However, specific details of this conquest and migration are often scarce in historical records, leaving much open to interpretation.

When the Romans finally conquered Pannonia in 8 AD, the Boii seem not to have opposed them. Their former territory was now called deserta Boiorum (deserta meaning 'empty or sparsely populated lands').

However, the Boii had not been exterminated: There was a civitas Boiorum et Azaliorum (the Azalii being a neighbouring tribe) which was under the jurisdiction of a prefect of the Danube shore (praefectus ripae Danuvii). This civitas, a common Roman administrative term designating both a city and the tribal district around it, was later adjoined to the city of Carnuntum.

Plautus
Plautus refers to the Boii in Captivi: "At nunc Siculus non est, Boius est, Boiam terit

(Translation:) But now he is not a Sicilian – he is a Boius, he has got a Boia woman."

There is a play on words: Boia means 'woman of the Boii', also 'convicted criminal's restraint collar'.

Livy
In volume 21 of his History of Rome, Livy (59 BC – 17 AD) claims that it was a Boio man that offered to show Hannibal the way across the Alps. "When, after the action had thus occurred, his own men returned to each general, Scipio could adopt no fixed plan of proceeding, except that he should form his measures from the plans and undertakings of the enemy: and Hannibal, uncertain whether he should pursue the march he had commenced into Italy, or fight with the Roman army which had first presented itself, the arrival of ambassadors from the Boii, and of a petty prince called Magalus, diverted from an immediate engagement; who, declaring that they would be the guides of his journey and the companions of his dangers, gave it as their opinion, that Italy ought to be attacked with the entire force of the war, his strength having been nowhere previously impaired."

Inscriptions
In the first century BC, the Boii living in an oppidum of Bratislava minted Biatecs, high-quality coins with inscriptions (probably the names of kings) in Latin letters. At the oppidum of Manching there was a ceramic found bearing the labeling "Boius" or "Baius" which is being displayed at the local Celts and Romans museum.

title: Boii