6. Binary Search Tree

Binary Tree

Properties

(H: height, N = number of nodes)

1. max Height = N

2. min Height

3. max N

4. balance

5. nearly complete: has the min height for its nodes && all nodes in the last level are found on the left

6. complete tree: has max num of entries for its height

 

Binary Tree Traversals

1. depth first traversal:

root to most distant descendent 을 먼저 탐색하고 second child 부터 아래로 탐색

1) preorder traversal(NLR): root -> left subtree -> right subtree (processed recursively)

2) inorder traversal: left subtree -> root -> right subtree

- trace from the root to the far-left left node

3) postorder traversal (LRN): left subtree -> right subtree -> root

 

 

2. breadth first traversal:

root to all of its children, then to children's children

 

Binary Search Tree

Properties

- All items in the left subtree are less than the root.

- All items in the right subtree are greater than or equal to the root

- Each subtree is itself a binary search tree

 

BST Operations

1. Traversal:

- inorder traversal produces a sequenced list

2. Search:

- find smallest node

- find largest node

- BST search

3. Insertion:

- how to: follow the branches to an empty subtree and insert the new node.

4. Deletion:

- first locate the node to be deleted

- 4 cases:

1.  has no children -> just delete
2.  has only right tree -> delete the node and attach the right subtree to deleted node's parent
3.  has only left tree -> delete the node and attach the left subtree to deleted node's parent
4.  has two subtrees -> find the data to be put instead of the deleted node. -> two choices: a) choose the largest node of the left subtree or b) the smallest node of the right tree