二分木

リストに似たデータ構造で、一つのノードが親と子供二人を持つもの。

struct Node {
    Node* parent;
    Node* leftChild;
    Node* rightChild;
};

データを格納するときは、左の子は自分より小さい値を、右の子は自分より大きい値になるようにする。このようにしておけば検索で値の大小を比較してノードをたどれるのでO(logN)ですむ。