Описание тега binary-tree
Binary trees are data structures in which each node has at most two child nodes, called the left child and the right child of the node. Nodes with children are called parent nodes, the node without a parent is called the root node, while nodes with no children are called leaf nodes. The level of a node is how far it is below the root node; the height of a node is how far it is above the furthest leaf.
One use of binary trees is efficient searching and sorting (e.g. binary search tree). The properties of trees mean nodes can be found quickly and compared easily, especially for trees which are balanced. (A tree is balanced if there is a similar number of right children as left children for each node.)
Types of binary trees:
- Red/black trees
- Interval trees
- Binary search trees
- Segment trees
- AVL trees
- AA trees
- Splay trees
- Scapegoat trees
- Treap
Binary trees can also be classified root, full, complete,... depending on whether they might specific rules regarding the number of existing child nodes.