DinS Written on 2017/4/29
1. Visually, what is a binary search tree(二叉搜索树)?
See featured image above.
Some notations to introduce. First, to simplify the graph, I didn’t write the parent, lc, rc and arrows explicitly. I think after reading the binary tree page you should know all those stuffs. Second, the number on the node stands for the key of the node. B.S.T. follows call-by-key, which means each data has a key to mark itself and we use the key to access the data. In other words, data are organized by the key. Third, the circle node shows that this node has at least one child. The square node shows that this node has no child and it’s a leaf node.
I should mention the relationship between binary tree, binary search tree and balanced binary search tree(平衡二叉搜索树) too.
This picture should be enough to convey the message.
2. Search Tree Property
This Property is what differs B.S.T from binary tree. Assuming identical keys are not allowed, the Property can be given as follows:
For any given node in a binary search tree, all keys in the left subtree must be less than this node, and all keys in the right subtree must be bigger than this node. (顺序性)
This property gives a sense of order to the binary tree. We can feel intuitively that as long as this property is maintained, there’ll be some shortcuts to operations on binary search tree.
Let’s check whether this tree meets the property.
Take the node 13 as an example. In the right subtree there’s only a 47 node, and 47 is bigger than 13. In the left subtree there are two nodes: 7 and 10. They are all smaller than 13. That means the node 13 passes the test. If we apply this test to all the other nodes in this tree, they’ll all pass. This tree is indeed a B.S.T.
3. Search
We can apply binary search in a B.S.T because the Search Tree Property ensures this will success.
On each node, by comparing the key of the node and the key of target, we can know whether to go to the left subtree or the right subtree.
Pseudo codes:
| BinSearchBST (BST, target)
| {
| x = BST -> root
| while (Exist(x))
| {
| if (x == target) return x
| if (target < x ) x = x->lc
| else x = x->rc
| }
| return null
| }
e.g. Search 10 in this B.S.T.
First we compare the root 5 with 10. Since 10 >5 we go to the right child of node 5.
Second we compare the node 13 with 10. Since 10 < 13 we go to the left child of node 13.
Third we compare the node 7 with 10. Since 10 > 7 we go to the right child of node 7.
Finally we compare node 10 with 10. Since 10 = 10, we have found the node we want.
One more word. If we perform BinSearchTree(11), after comparing node 10 we go to the right child of node 10, which is a null. This will end the while() and report failure.
What’s the efficiency of search operation? In the worst case such as failure, we have to go to the bottom of the tree. This means O(height) time.
4. Min and Max
Search for minimum and maximum is basically the same.
To get the minimum, we just need to go along the left child until we can’t get anywhere. Then we return the last node visited.
Pseudo codes:
| MinBST(BST)
| {
| x = BST -> root
| while (Exist(x))
| {
| x = x -> lc
| }
| return x -> parent
| }
To get the maximum, replace the left child with right child in MinBST.
Pseudo codes:
| MaxBST(BST)
| {
| x = BST -> root
| while (Exist(x))
| {
| x = x -> rc
| }
| return x -> parent
| }
As we must travel to the leaf of BST, these two operations need O(height) time.
5. Insert
To insert a new node, follow these two steps:
(1) Search for key k and end at a null. That’s where we’ll insert the new node.
(2) Rewire the proper node with node k.
These two steps won’t break Search Tree Property. Done.
Pseudo codes:
| InsertBST(BST, key)
| {
| x = BinSearchBST (BST, key)
| if (x == key) return
| rewire(x -> parent, key)
| }
e.g. Insert a new node 6 to a BST.
First we search for key 6 in the BST and end up with a null.
Next, since now x is null, we need to rewire x’s parent with the new node 6.
Here we can see Search Tree Property is maintained. As why is this the case, aftering calling BinSearchBST() the position we have found must be a legal one for this new key. If we rewire it to the tree, nothing will happen to the Property.
Rewire takes O(1) and search takes O(height). In conclusion insertion in BST takes O(height).
This article continues at Binary Search Tree – Part B.