Software Engineering Body of Knowledge (v3) (2014) (811503), страница 75
Текст из файла (страница 75)
The root node isat level 0. Alternately, the level of a node X is thelength of the unique path from the root of the treeto node X.For example, root node A is at level 0 in Figure 14.15. Nodes B, C, and D are at level 1. Theremaining nodes in Figure 14.15 are all at level 2.The height of a tree is the maximum of the levels of nodes in the tree.For example, in Figure 14.15, the height of thetree is 2.A node is called a leaf if it has no children. Thedegree of a leaf node is 0.For example, in Figure 14.15, nodes E throughK are all leaf nodes with degree 0.The ancestors or predecessors of a nonrootnode X are all the nodes in the path from root tonode X.For example, in Figure 14.15, nodes A and Dform the set of ancestors for J.The successors or descendents of a node X areall the nodes that have X as its ancestor. For a treewith n nodes, all the remaining n − 1 nodes aresuccessors of the root node.For example, in Figure 14.15, node B has successors in E, F, and G.If node X is an ancestor of node Y, then node Yis a successor of X.Two or more nodes sharing the same parentnode are called sibling nodes.For example, in Figure 14.15, nodes E and Gare siblings.
However, nodes E and J, thoughfrom the same level, are not sibling nodes.Two sibling nodes are of the same level, buttwo nodes in the same level are not necessarilysiblings.A tree is called an ordered tree if the relative position of occurrences of children nodes issignificant.For example, a family tree is an ordered treeif, as a rule, the name of an elder sibling appearsalways before (i.e., on the left of) the youngersibling.In an unordered tree, the relative position ofoccurrences between the siblings does not bearany significance and may be altered arbitrarily.A binary tree is formed with zero or more nodeswhere there is a root node R and all the remainingnodes form a pair of ordered subtrees under theroot node.14-12 SWEBOK® Guide V3.0In a binary tree, no internal node can have morethan two children. However, one must considerthat besides this criterion in terms of the degreeof internal nodes, a binary tree is always ordered.If the positions of the left and right subtrees forany node in the tree are swapped, then a new treeis derived.Figure 14.18.
Example of Complete Binary TreesFigure 14.16. Examples of Binary TreesFor example, in Figure 14.16, the two binarytrees are different as the positions of occurrencesof the children of A are different in the two trees.Figure 14.17. Example of a Full Binary TreeAccording to [1*], a binary tree is called a fullbinary tree if every internal node has exactly twochildren.For example, the binary tree in Figure 14.17is a full binary tree, as both of the two internalnodes A and B are of degree 2.A full binary tree following the definitionabove is also referred to as a strictly binary tree.For example, both binary trees in Figure 14.18are complete binary trees. The tree in Figure14.18(a) is a complete as well as a full binarytree. A complete binary tree has all its levels,except possibly the last one, filled up to capacity.In case the last level of a complete binary tree isnot full, nodes occur from the leftmost positionsavailable.Interestingly, following the definitions above,the tree in Figure 14.18(b) is a complete but notfull binary tree as node B has only one child in D.On the contrary, the tree in Figure 14.17 is a full—but not complete—binary tree, as the childrenof B occur in the tree while the children of C donot appear in the last level.A binary tree of height H is balanced if all itsleaf nodes occur at levels H or H − 1.For example, all three binary trees in Figures14.17 and 14.18 are balanced binary trees.There are at most 2H leaves in a binary tree ofheight H.
In other words, if a binary tree with Lleaves is full and balanced, then its height is H =⎡log2L⎤.For example, this statement is true for thetwo trees in Figures 14.17 and 14.18(a) as bothtrees are full and balanced. However, the expression above does not match for the tree in Figure14.18(b) as it is not a full binary tree.A binary search tree (BST) is a special kind ofbinary tree in which each node contains a distinctkey value, and the key value of each node in thetree is less than every key value in its right subtreeand greater than every key value in its left subtree.A traversal algorithm is a procedure for systematically visiting every node of a binary tree.Tree traversals may be defined recursively.If T is binary tree with root R and the remaining nodes form an ordered pair of nonnull leftsubtree TL and nonnull right subtree TR below R,then the preorder traversal function PreOrder(T)is defined as:PreOrder(T) = R, PreOrder(TL), PreOrder(TR) … eqn.
1Mathematical Foundations 14-13The recursive process of finding the preordertraversal of the subtrees continues till the subtrees are found to be Null. Here, commas havebeen used as delimiters for the sake of improvedreadability.The postorder and in-order may be similarlydefined using eqn.
2 and eqn. 3 respectively.PostOrder(T) = PostOrder(TL), PostOrder(TR),R … eqn 2InOrder(T) = InOrder(TL), R, InOrder(TR) …eqn 3Figure 14.19. A Binary Search TreeFor example, the tree in Figure 14.19 is a binarysearch tree (BST). The preorder, postorder, andin-order traversal outputs for the BST are givenbelow in their respective order.Preorder output: 9, 5, 2, 1, 4, 7, 6, 8, 13, 11,10, 15Postorder output: 1, 4, 2, 6, 8, 7, 5, 10, 11, 15,13, 9In-order output: 1, 2, 4, 5, 6, 7, 8, 9, 10, 11,13, 15Further discussion on trees and their usage hasbeen included in section 6, Data Structure and Representation, of the Computing Foundations KA.6. Discrete Probability[1*, c7]Probability is the mathematical description ofrandomness.
Basic definition of probability andrandomness has been defined in section 4 of thisKA. Here, let us start with the concepts behindprobability distribution and discrete probability.A probability model is a mathematical description of a random phenomenon consisting of twoparts: a sample space S and a way of assigningprobabilities to events. The sample space definesthe set of all possible outcomes, whereas an eventis a subset of a sample space representing a possible outcome or a set of outcomes.A random variable is a function or rule thatassigns a number to each outcome. Basically, itis just a symbol that represents the outcome of anexperiment.For example, let X be the number of headswhen the experiment is flipping a coin n times.Similarly, let S be the speed of a car as registeredon a radar detector.The values for a random variable could be discrete or continuous depending on the experiment.A discrete random variable can hold all possible outcomes without missing any, although itmight take an infinite amount of time.A continuous random variable is used to measure an uncountable number of values even if aninfinite amount of time is given.For example, if a random variable X representsan outcome that is a real number between 1 and100, then X may have an infinite number of values.
One can never list all possible outcomes forX even if an infinite amount of time is allowed.Here, X is a continuous random variable. Onthe contrary, for the same interval of 1 to 100,another random variable Y can be used to list allthe integer values in the range. Here, Y is a discrete random variable.An upper-case letter, say X, will representthe name of the random variable. Its lower-casecounterpart, x, will represent the value of the random variable.The probability that the random variable X willequal x is:P(X = x) or, more simply, P(x).A probability distribution (density) function isa table, formula, or graph that describes the values of a random variable and the probability associated with these values.14-14 SWEBOK® Guide V3.0Probabilities associated with discrete randomvariables have the following properties:i.
0 ≤ P(x) ≤ 1 for all xii. ΣP(x) = 1A discrete probability distribution can be represented as a discrete random variable.X123456P(x)1/61/61/61/61/61/6Figure 14.20. A Discrete Probability Function for a RollingDieThe mean μ of a probability distribution modelis the sum of the product terms for individualevents and its outcome probability.
In otherwords, for the possible outcomes x1, x2, … , xnin a sample space S if pk is the probability of outcome xk, the mean of this probability would be μ= x1p1 + x2p2 + … + xnpn.For example, the mean of the probability density for the distribution in Figure 14.20 would be1 * (1/6) + 2 * (1/6) + 3 * (1/6) + 4 * (1/6) + 5* (1/6) + 6 * (1/6)= 21 * (1/6) = 3.5Here, the sample space refers to the set of allpossible outcomes.The variance s2 of a discrete probability modelis: s2 = (x1 – μ)2p1 + (x2 – μ)2p2 + … + (xk – μ)2pk.The standard deviations is the square root of thevariance.For example, for the probability distribution inFigure 14.20, the variation σ2 would bes2 = [(1 – 3.5)2 * (1/6) + (2 – 3.5)2 * (1/6) +(3 – 3.5)2 * (1/6) + (4 – 3.5)2 * (1/6) + (5 –3.5)2 * (1/6) + (6 – 3.5)2 * (1/6)]= (6.25 + 2.25 + 0.25 + 0.5 + 2.25 + 6.25) *(1/6)= 17.5 * (1/6)= 2.90∴ standard deviation s =These numbers indeed aim to derive the average value from repeated experiments.
This isbased on the single most important phenomenon of probability, i.e., the average value fromrepeated experiments is likely to be close to theexpected value of one experiment. Moreover,the average value is more likely to be closer tothe expected value of any one experiment as thenumber of experiments increases.7. Finite State Machines[1*, c13]A computer system may be abstracted as a mapping from state to state driven by inputs. In otherwords, a system may be considered as a transitionfunction T: S × I → S × O, where S is the set ofstates and I, O are the input and output functions.If the state set S is finite (not infinite), the system is called a finite state machine (FSM).Alternately, a finite state machine (FSM) is amathematical abstraction composed of a finitenumber of states and transitions between thosestates.
If the domain S × I is reasonably small,then one can specify T explicitly using diagramssimilar to a flow graph to illustrate the way logicflows for different inputs. However, this is practical only for machines that have a very smallinformation capacity.An FSM has a finite internal memory, an inputfeature that reads symbols in a sequence and oneat a time, and an output feature.The operation of an FSM begins from a startstate, goes through transitions depending on inputto different states, and can end in any valid state.However, only a few of all the states mark a successful flow of operation.
These are called acceptstates.The information capacity of an FSM isC = log |S|. Thus, if we represent a machine havingan information capacity of C bits as an FSM, thenits state transition graph will have |S| = 2C nodes.A finite state machine is formally defined as M= (S, I, O, f, g, s0).S is the state set;I is the set of input symbols;O is the set of output symbols;f is the state transition function;Mathematical Foundations 14-15g is the output function;and s0 is the initial state.Given an input x ∈ I on state Sk, the FSMmakes a transition to state Sh following state transition function f and produces an output y ∈ Ousing the output function g.The state transition and output values for different inputs on different states may be representedusing a state table. The state table for the FSM inFigure 14.21 is shown in Figure 14.22. Each pairagainst an input symbol represents the new stateand the output symbol.For example, Figures 14.22(a) and 14.22(b) aretwo alternate representations of the FSM in Figure 14.21.8. GrammarsFigure 14.21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
