Full Binary Tree
A binary tree is full if each node has 0 or 2 children. We can also say that a full binary tree is a binary tree in which all the nodes, except the leaves, have two children.
Here are examples of full binary trees.
Complete binary tree
A binary tree is complete if all the levels are completely filled, except maybe the last level and the last level has all the keys as left as possible.
Perfect binary tree
A binary tree is perfect if all the internal nodes have two children and all the leaves are on the same level.
A perfect binary tree of height h a \(2^h - 1\) node.
Balanced binary tree
A binary tree is balanced if its height is \(O(log n)\), where n is the number of nodes.
- AVL trees maintains the height in \(O(log n)\) while ensuring that the difference between the heights of the left and right subtrees is 1.
- The red-black trees maintain the height in \(O(log n)\) ensuring that the number of black nodes on each root-to-leaf path is the same and that there are no adjacent red nodes.
Binary balanced search trees are good from a performance point of view because they provide \(O(log n)\) time for searching, inserting and deleting.