Attribute reduction plays an essential role in rough set. Discernibility matrix provides a good way for attribute reduction in rough set, but there are many redundancy and pointless nonempty elements in discernibility matrix, such as duplications and supersets. In order to eliminate these redundancies and pointless elements, a discernibility information tree is proposed, which is an extended order-tree, and can be easy to fully and partly eliminate duplicates of elements and supersets of elements in discernibility matrix efficiently. In order to efficiently utilize the dicernibility information tree structure for attribute reduction, an attribute reduction complete algorithm is developed, and it’s complexity is reduced to ??(∣??∣∣??∣²).