Grafting (algorithm)

In computer science, grafting is a method used to manipulate trees. One such tree is an ordered tree, which is where the subtrees for any node are ordered. Let root(T₁), ..., root(T_n) be the children of root(T) and root(T_i) be the ith child. A suitable representation of ordered trees is to make them a rooted binary tree, where each node is stored in the same amount of memory.^[1]

The conversion to a rooted binary tree root(T) is:

1. For each child of root(T), remove all the edges from the child to the parent.
2. For each node:
  a. Add an edge to the first child (if one exists) as the left child.
  b. Add an edge to the next sibling (if one exists) as the right child.

Grafting can identify regions where there are no occupancies and correct the poor class assignments to increase accuracy. The extension to graft multiple branches at each leaf reduces the number of errors.^[2]

See also

• Grafting and pruning for decision trees
• Left child-right sibling binary tree

References

1. ↑ http://acm.pku.edu.cn/JudgeOnline/problem?id=3437 Peking University
2. ↑ http://www.answers.com/topic/grafting-computer Grafting (computer)