Data Struct – Pert 04
Binary Search Tree
Binary search tree (binary search tree, or BST) is a binary tree data structure that has properties as follows:
Each node has a value.
A total arrangement specified in this value.
Sub left tree of a node only contains a smaller value than the value of the node.
Sub tree right of a node contains only values greater than or equal to the value of the node.
2. Pre-order
Print data on root
Recursively print all the data in the left subtree
Recursively print out all the data on the right subtree
3. In-order
Recursively print all the data in the left subtree
Print data on root
Recursively print out all the data on the right subtree
4. Post-order
Recursively print all the data in the left subtree
Recursively print out all the data on the right subtree
Print data on root
5. Insert BST
Insertion of a new node, preceded by a search operation the appropriate position. In this case the new node will be a leaf / leaf.
6. Delete BST
Delete operation has three possibilities:
– Delete the node without children / child (leaf / leaf): node can be instantly removed
– Delete the node with one child / child: the child node will replace him.
– Delete the node with two children / child: then the node will be replaced by the leftmost node of Sub Tree Right or can also be replaced by the rightmost child of Sub Tree Left.