I am Sungjin Park.

3 minute read

Binary Tree

Binary Tree’s each node can only have 0, 1, or 2 nodes as a child and a child only can have one parent.

Perfect Binary Tree

  • Number of nodes in a same level is double of one before. 1→2→4→8→16 and so on

  • last level’s number of nodes = all nodes before +1.

    (1 + 2 + 4) + 1= 8

  • If the tree forms a perfect triangular shape, it is a perfect binaree tree.

Time Complexity of Binary Tree (perfect)

  • Lookup - O(log n)
  • Insertion - O(log n)

  • Deletion - O(log n)

    Insertion and Deletion takes O(log n) for BST because it has to lookup first before it finds place to add or delete nodes.

Binary Search Tree (BST)

Why use BST over Hash Table?

  • BST preserves relationships between elements.

To understand the relationship, we need to see the rules of BST.

  1. All child node on the right must be greater than the current node. (left must be smaller)
  2. Node only can have up to 2 children.

It’s all about higher or lower, bigger or smaller. If the element is bigger, it has to be on the right.

Balanced VS Unbalanced BST

why is unbalanced BST bad?

Data might get stored in one big line of tree and it basically turns in to a linked list which has slower lookup speed O(n).

  • It is important to keep BST balanced to have the best performance.

Pros

  • Better than O(n)
  • Ordered
  • Flexible size

Cons

  • No O(1) operations

AVL Tree and Red-Black Tree

They keep the tree self-balanced to ensure O(log n) time-complexity.

AVL is more strictly balanced.

  • additional rotations needed, which means insert and delete operation will slightly slower.

Red-Black may not remain balanced.

  • faster in terms of inserting and deleting.
  • Used in Java to implement TreeMap and TreeSet.

Use AVL Tree when ‘searching’ is more emphasized.

Use Red-Black Tree when inserting and deleting is more emphasized.

Binary Heaps

Looks like BST, but it only have rules that the parent node is bigger / smaller than the children.

Commonly used in priority Queues(queues with priorities), data storage, sorting algorithms

good at comparing operation.

Pros

  • Bettern than O(n)
  • Priority
  • Flexible size
  • Fast insert

Cons

  • Slow lookup. O(n)

Trie

Mostly used in string problem. ex) auto-suggestion in Google search.

Think of two words that start with ‘a’. Let’s say they are ‘ant’ and ‘apple’.

‘a’ will be the parent of ‘n’ and ‘p’ node.

‘n’ will have ‘t’ as a child. ‘p’ will have ‘p’, ‘l’, ‘e’ nodes going done the tree.

You may also enjoy