Binary search tree. Internal representation
Like any other dynamic data structure, BST requires storing of some additional auxiliary data, in order to keep its structure. Each node of binary tree contains the following information:
- a value (user's data);
- a link to the left child (auxiliary data);
- a link to the right child (auxiliary data).
With a view to internal representation, the sample from the overview changes:
Leaf nodes have links to the children, but they don't have children. In a programming language it means, that corresponding links are set to NULL.
Code snippets
It is a routine, when the whole structure of BST is put into two classes. Main class BinarySearchTree is a public interface and BSTNode mean for private use inside the main class. This division is necessary, because some operations, like removal, may result in an empty tree, which means that tree even doesn't have a root node.
Java
public class BSTNode {
private int value;
private BSTNode left;
private BSTNode right;
public BSTNode(int value) {
this.value = value;
left = null;
right = null;
}
}
public class BinarySearchTree {
private BSTNode root;
public BinarySearchTree() {
root = null;
}
}
C++
class BSTNode {
private:
int value;
BSTNode* left;
BSTNode* right;
public:
BSTNode(int value) {
this->value = value;
left = NULL;
right = NULL;
}
};
class BinarySearchTree {
private:
BSTNode* root;
public:
BinarySearchTree() {
root = NULL;
}
};
Recommended books
- Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
- Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
- Robert Lafore. Data Structures and Algorithms in Java. (Practice)
- Mark Allen Weiss. Data Structures and Problem Solving Using C++.(Practice)
| Previous: Binary search tree overview | Next: Adding a value |
Contribute to AlgoList
Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.
Every dollar helps!