Hello everyone. We’re going to learn
Chapter 5 Binary Tree of Data Structure and Algorithm. Today, we’re going to introduce a very important data structure — binary search tree.
The abbreviation of binary search tree is BST. Its property is that if its left subtree is not null,
the keys of its left subtree is all
smaller than that of the current node, and the keys
of its right subtree is larger than
that of current node. Every root of subtree has this property.
Thus, if we have a in-order traversal in the BST,
we’ll get a increasing sequence.
In this example,
the keys of the BST are all string.
And we can see the tree meets the property of BST,
and its in-order traversal sequence is a lexicographically increasing sequence.
The most important feature of BST is that its retrieval performance is very good. If the tree
is short, that is its height is order of log n,
then we can finish our retrieval job in O(log n) time.
Like the binary search, when
retrieving a key, we just need to
search one of its subtree for every node, that is
if I find the key is smaller than the key of the root,
we just need to search the left subtree, and otherwise we just need to search the right one. For example, we search the key 19,
it’s smaller than the key 35 of the root,
then we enter the left subtree, the key is 16 here. For 19 is larger than 16, we enter the right subtree, and find 19.
This is a very fast retrieval process.
Insertion is in fact a process of retrieval.
It’s not permitted that the key for insertion is already in the tree,
Because, in general speaking, it’s not permitted that duplicated keys are in the tree.
For insertion process of 17,
we start from root, we enter the node with key 16 for 17 is smaller than 35.
We enter the node with key 19, for it’s larger than 16. And then we want to enter the left subtree of 19.
However, it’s null, the whole process is actually a failed retrieval process.
In this case, we can add a new leaf at the position that we
failed retrieval.
We can see in this process, that we keep the property of BST,
can we ensure the performance of BST, that is the time complexity is also O(log n).
And for each insertion, the time complexity is O(1), so the total time of insertion is order of log n.
Let’s see the process of deletion.
For such a BST, we want to delete node with key wan,
the node doesn’t have left subtree,
so we can use the its whole right subtree
to replace the original position of that node.
Similarly, if
if doesn’t have right subtree, we can use its non-null left subtree to replace its position.
So, it’s very easy to finish this process of deletion.
Then we’re going to see a little more complex case — delete the node with key zol. ======46
if we want to delete zol
and keep the property of BST,
that is, maintain the order of in-order sequence of the tree,
we consider to find the
the node with maximum key in the left subtree or node with minimum key in the right subtree.
For example, if we want to find the node with the maximum key, zi, in the left subtree，the node
should have no right child. Thus, we can move
the original right subtree of zol to
the right of the node with maximum key zi
to be its right subtree.
We can see the operation obviously
doesn’t have good performance. Though it in fact keeps a property.
The height of tree is order of log n before,
and the node with key zol deleted is close to the root,
and the node with key yo is also close to the root. So the difference between the height of these nodes and the whole tree is little.
And we move the whole subtree with the node zol, and the height of the subtree of node yo
is multiplied by 2, so the height of the whole tree is nearly multiplied by 2 as well.
So the time complexity of
the retrieval process after is also multiplied by 2.
So we’re going to introduce a more effective way to delete.
Using this way will keep the performance of manipulations on the original BST.
Similarly, we should find
the node with maximum key in the left subtree of the node to be deleted, or the minimum key in the right subtree.
If we’re only given the key of that node, and you should
find the node in the BST first, and then delete it.
So in the recursion, we should find the node first.
If the key of that node is
smaller than the key of root of the subtree, we enter the
left subtree and do the same thing recursively, or if larger we enter the right one. If the two keys are equal,
then we have found the node to be deleted. When we find the node,
if its left subtree is null, as the example
we mentioned before, the node with key wan.
Its left child is null, so we can simply use its right child to replace it
to finish the deletion. Otherwise,
if its left child isn’t null,
we should examine whether its right child is null.
If the right child is null, then similarly we can replace the node by its non-null left child.
Otherwise, if the right child is not null either,
we should find the the node with minimum key in the right subtree
for replacing. This is what we find
the node with minimum key in its right subtree, we save it in variable temp.
Then we replace the key of the node to be deleted G
by the key of node saved in temp.
And then we delete the node saved in temp,
and replace it with its
right child.
And then we finish the replacement process.
It’s finished by the function deletemin.
And what we pass to deletemin before
is G’s right child J.
After we pass the argument, the function is in fact
implemented by recursion, however,
we can also use iteration to implement it. We enter
the left child of the current node starting from J recursively,
until we can’t do this, and in fact G is
the node with minimum key in the right subtree.
We find the node and save it in the temp.
Meanwhile, its right child is used by us
to replace the H,
that is the position in which the key of the node is minimum. Why can we do this?
Because the H we delete before is a node without left child.
So it’s the same case as the case with wan.
So we summarize the property of binary search tree.
First, it’s a very good structure used to index and often used to organize data in the internal storage.
However, in some case the BST
may deteriorate, so we have some varieties such as red-black tree and splay tree
that can maintain the balance of the tree.
In the external storage, we often use B/B+ tree to organize big data.
However, for the internal storage is cheaper and cheaper,
so in many cases we put the data in it,
and use B/B+ tree to organize them too.
We should pay more attention to that
we should always keep the property and performance of the BST. For the delete algorithm
we mentioned before, if we use the first scheme, the performance won’t be very good,
and it will affect the performance of retrieval and the height of the tree.
Think about these questions. First, how can we prevent
that the tree become linear, for example, if
we insert nodes with key increasingly one by one, then we will form a linked list.
The second question is, in general speaking, the same keys in the tree are not allowed,
if some keys is truly the same in the tree,
how can we handle this case? What rule should we formulate
to make the insertion, deletion and retrieval can still be finished efficiently.
Thank you all!