Hello everyone. In this lecture of Data Structure and Algorithm,
we’re going to learn the chapter 5 binary tree.
We’re going to mainly talk about the storage structure of binary tree.
Binary tree is a complex nonlinear structure.
For such a complex structure, in general speaking,
we can’t use a sequenced structure to store it.
We often use dynamic link method to store.
For binary tree, every node has information on left and right children.
Thus, binary linked list is a more convenient way to
store it. We also need to store
the data domain info of every node. Currently, a lot of people prefer to use a trinomial linked list to from the binary tree.
That is add pointer to parent node to every node.
What is the benefit using such a domain? The main benefit
is it’s more convenient to find its parent node and
sibling nodes than binary one.
Let’s see the storage structure of
binary linked list. The binary tree is on the left,
and the corresponding storage structure is on the right.
We can see lots of pointers of the left and right children domain of nodes
are null. We can say nearly half of these nodes are null.
Let’s see the form of trinomial linked list. Its main
improvement is we can conveniently access
up to the root by the parent pointer.
Of course, we can also access nodes of
the path from the node to the root and their sibling nodes conveniently.
But if we delete some node in the tree,
we should maintain the parent pointer.
So how can we implement the storage structure of binary linked list?
In fact, based on the ADT of node of binary tree we defined before,
besides info,
we add up left and right
these 2 pointer. In this
implementation of binary linked list
how can we find the father node of a node?
We notice that there isn’t a pointer to father node,
so we just can find its father node from the root node.
Let’s see a recursive version of implementation.
We start from
the root of a subtree. It’s recursive, so at first we pass the root of whole tree to the function. And in every process, it passes the root of its subtrees to it.
If the root of subtree is not null,
we examine whether the son of the current node is what we want.
If it’s true, the root of subtree is the father node we want.
If not, we’ll go down to
the left child and right child of this node respectively
to continue out finding. We can pay more attention to this framework,
it’s actually a framework of pre-order traversal.
This is a recursive process for left child, and this is for right child.
The most important part of the manipulation of nodes
is here before these two recursions.
It replaces the
the position of visit in the recursive version of pre-order traversal.
We discovered the framework of the algorithm and what traversal we should use to traverse.
The algorithm before is implemented by recursion, think about
can we implement a non-recursive version? Moreover, can we implement it using BFS?
There is a general framework for this algorithm.
The mainly purpose of this framework is to find the father node, and finding sibling node
is also implemented by similar framework. Now we’re going to see how we can implement a non-recursive version,
we’ll use the framework of non-recursion. It is corresponded
to the framework of pre-order traversal, so we use the framework of non-recursive pre-order traversal.
At the beginning, we assign the root node
to a temporary pointer. And then
we save a lookout to the stack.
Then we find in the subtree of the temporary pointer. If the left or right child
of the temporary pointer is what we need to find,
then pointer is the father node of current.
If not found, then we should think about
what we should do next. We should save
the non-null right child of pointer, and we can now
enter its left subtree. Therefore, after we access all the nodes in the left subtree,
we can pop the right child from the stack and continue to access the right subtree. Thus,
we should push the non-null right child to the stack.
And then we enter the non-null left child.
If the right child is null, that means we have accessed all the nods of left subtree,
we should pop some information on right child to be
accessed. And then pop it and repeat the process.
Let’s analysis the space complexity of binary linked list.
First, we should pay attention to these conceptions.
The density of storage describe the efficiency of storage.
That is the the percentage of effective data in all the data. The structural cost is the cost
of auxiliary information we saved to save all the effective data.
The auxiliary information occupy some percentage of the data structure.
For binary linked list,
according to Full Binary Tree Theorem, we can see half of pointer domains is null.
For each node, we should save 2 pointer domains and 1 data domain.
Suppose the sizes of pointer domain and data domain is equal, then the structural code is
2/3, the density of storage is only 1/3.
How can we improve the efficiency of storage?
In C and C++, for example in C we can use
union to define the structure. It seems that branch nodes and leaf nodes can be unified.
And we can find what nodes contain less information,
and find a way to store information effectively. However, in fact,
there is a property in union that the preserved space for
union is equal to the size of largest type.
So we just unify the express form of node, but
there is not significant improvement. And in C++,
we can use subclass and virtual function to implement, and we only distinguish them in concept.
However, there isn’t significant improvement in storage either.
In the early age, there may be some ways to improve the efficiency of storage due to the limit of internal memory resource.
We can just store the value of leaf nodes in its father,
rather than store a pointer. And for a leaf node,
its pointers only point to null, and it wastes a lot of memory.
Of course, we should distinguish saving other data from
saving true pointer, we should have some way to mark.
For saving memory, we directly use pointer itself to do this.
This size of pointer is usually very large,
it’s normally 4 bytes or 8 bytes, and its higher bits are always 0.
And we use the highest bit to be the flag bit. However, using this method
makes the whole algorithm hard to write, read and maintain. So we don’t use this method often now.
Well, we can use a ordered array to store some special binary trees.
For example, complete binary tree can be stored in a array.
Because the complete binary tree is full of nodes
from root to leaves, from left to right. Thus,
we can put all the nodes to an array
according to its ID.
It’s a linear structure in memory, but it’s still a binary tree structure logically.
Meanwhile, we can easily calculate the subscript of its children
by subscript of the node.
Now let’s see the formula of the subscript of complete binary tree.
For a complete binary tree, we usually count the subscript from 0, since there are some
people counting from 1. Then, in such a complete binary tree, we can see
nearly half of them don’t have children.
For the other half of nodes, they have children.
The subscript of the left child of node i is 2i+1,
and that of right child is 2i+2.
For the father,
the subscript is ⌊(i-1)/2⌋.
And in our numbering system, the subscript of left child is always odd.
And for right child, its subscript is even.
Thus, for a node with odd subscript i,
the subscript of its right sibling is i+1.
For a node with even subscript i, we can use subscript i-1
to find its left sibling. So we can easily know the logical relationship between them.
Here are some questions.
The first one is the algorithm in textbook is usually written using
the binary linked list form. So if we use trinomial linked list,
what changes should we make to the algorithm?
We should pay more attention to maintain the father pointer.
And for complete trinomial tree,
can we derive a similar subscript formula for it?
Of course we store the tree in an array.
Thank you all!