Trees

Concept

계층 데이터 구조, parent-child 구조를 나타내는 nodes와 link로 구성. Special case of graphs with a hierarchical structures but without loops.

Terminology

Root : node without a parent, Leaf : node without children, Internal node: node with at least one child, Height : number of edges between a node and a leaf.

Binary Trees

최대 두개의 child를 가지는 tree.

순회 방식 : Preorder, inorder, and postorder.

Binary Search Trees

binary tree는 node에 key를 저장하고 다음 성질을 만족.

• node의 key는 left child의 key보다 크다.
• node의 key는 right child의 key보다 작다.
• node의 key는 left subtree의 node들의 key들보다 크고 right subtree의 node들의 key들보다 작다 => inorder traversal이 sorted order를 표현.

time complexity

• searching time complexity : O(h)
• insertion of a node time complexity : O(h)
• transplant(T,u,v) : O(1)

balance of trees

• order of insertion matters
• improving average case : randomized binary search trees
• height of each path from root to every leaf is asymptotically O(logn)
• ex) AVL Tree, Red-Black tree

Red-Black Trees

• Binary search tree with one extra bit per node for its color
• root에서 leaf까지의 거리가 다른 path의 거리보다 두배가 되지 않는다.
• black height란 해당 node에서 leafs노드까지 만나는 black node의 갯수.
• properties of red-black trees
• 1) Every node is either red or black
• 2) root is black
• 3) every leaf (NIL) is black
• 4) If a node is red, then both its children are black
• 5) For each node, all paths from the node to descendant has the same black height.