Grafting (algorithm)

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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(T1), ..., root(Tn) be the children of root(T) and root(Ti) 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[edit]


  1. ^ Peking University
  2. ^ Grafting (computer)