[Data Structure] Types of Trees

Rex Chiang

·

Follow

3 min read

·

Feb 12, 2023

--

Listen

Share

BST (Binary Search Tree)

• All values in the left child tree should less than the parent node’s value.
• All values in the right child tree should greater than the parent node’s value.
• Both the left and right child trees should be BST too.
• Average time complexity for search, insert and delete is O(Log n).
• Worst time complexity for search, insert and delete is O(n).

Balanced BST (Balanced Binary Search Tree)

• Follow extra conditions base on BST to improve time complexity.
• The height of the left and right tree for any node shouldn’t differ by more than 1.
• Both the left and right child trees should be Balanced BST too.
• Average time complexity for search, insert and delete is O(Log n).
• Worst time complexity for search, insert and delete is O(Log n).

B-Tree

• Traditional BST are efficient in terms of memory, but not in terms of hard disk.
• Traditional BST store each node in different hard disk block, and the block is the unit when accessing data.
• B-Tree try to fill up each node (block), and distinguish child nodes inside parent nodes to reduce disk I/O operations.
• All leaf nodes are at the same level.
• For a m levels B-Tree, below are its properties.
• Each node have at most m-1 keys.
• Each node have at most m child trees.
• All keys in nodes are sorted in increasing order.
• The child between two keys k1 and k2 contains all keys in the range from k1 to k2.
• All nodes should have complete data.

B+Tree

• B-Tree still has some problems in disk I/O operations.
• Access data has unstable times of disk I/O operations.
• Not efficient if need to search range of data if data distributed in different child tree.
• If data size increasing, parent node can only include less child nodes.
• Follow extra conditions base on B-Tree to solve above problems.
• Each non-leaf node can only store index instead of complete data to include more keys.
• Only leaf nodes have complete data would be more stable, because each accessing need to run till leaf node.
• Each leaf node has pointer to point to neighbor nodes, and can link each data in increasing order.