Join Raghavendra Dixit for an in-depth discussion in this video The tree data structure, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] In this chapter, we will learn binary trees, and more specifically, binary search trees. Binary search tree is a very versatile data structure. That is, it is really fast to insert items into it, it's fast to delete items from it, and it's pretty fast to search items in a binary search tree. If you compare sorted arrays and linked list data structures, we see that search is fast in a sorted array, but quite slow in a linked list. Inserting an item is slow in a sorted array, while it is very fast in case of a linked list that is if we insert the item at the head, alright? Then deleting an item is also slow, if we used a sorted array to sort items, while it is fast, if we used a linked list.
Binary search trees are very balanced in the sense that all these common operations like insert, delete, and search take about the same time, which is of the order of log n, alright? And we will see how to arrive at that slightly later in the chapter. So let's see what a tree data structure is, and know about some commonly used items related to it. A tree data structure may be visualized to be something like this, where we have the nodes, which contain the data.
And the nodes are connected to other nodes through what are called as the edges. And it's just like we connected the nodes of a link list through object references, okay? The node at the top of the tree is called the root node. And in a tree data structure, there can only be one root node. So, just as the link list data structure had a reference to the head node, a tree data structure has a reference to the root node.
And all the other nodes can be accessed through that. There is one more property of the tree data structure, and that is to search any node of the tree, there must be only one part from the root node, alright? For example, if these two nodes are connected, then to search the F node, we can start from the root node A, go to C and then F, or we start from A, then go to C, then G and then F. So there are multiple parts from the root node to reach the F node.
So that is not allowed in a tree data structure, alright? Any node other than the root has exactly one edge running upwards to another node. The node above is called the parent of the node. For example, the F node has exactly one edge running upwards to the C node. So, the C node is set to be the parent of F. Actually, C is the parent of both F and G nodes. So, F and G nodes are called the children of the C node.
Then a node which has no children is called a leaf node. Any node may be considered to be the root of a subtree, which consists of its children and its children's children and so on. The level of a node tells us how far it is from the root. For example, the root element is assumed to be at level zero. Children of root are set to be at level one. Then their children in turn are set to be at level two and so on.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.