Hello everyone
This lecture for the data structure and algorithm is balanced binary search tree in 12th chapter advanced data structure.
And we gonna learn about the deleting and efficiency analysis of AVL tree.
AVL tree is BST which requires that the difference of left subtree and right subtree is no more than one.
The deleting of AVL tree is a opposite operation of inserting.
AVL tree's deleting must obey the deleting property of BST.
Find the smallest element of the left subtree or the biggest element of right subtree.
Then replace the node that will be deleted.
It might lead to a reduction of local subtree's left branch or right branch after deleting.
The one, which is short before, might be shorter.
In this situation, it's unbalanced and need to be adjusted. And this adjustment is passed to the root.
Let's look at the situation of adjustment after deleting.
We must modify some balanced factor after deleting.
The current node is the father of the deleting node in lots of circumstance.
Its balanced factor was zero.
The balanced factor might be changed after deleting.
But its height might not be changed because another part wasn't deleted.
If it is, the current node whose balanced factor wasn't zero
The current node is unbalanced when the short side is deleted and cause the another side is shorter.
Then we need an adjustment. And the height of the subtree might be modified after adjustment.
It will influent its upper nodes after the height is decreased.
We need to check level by level for its balance.
We need to set a variable called modified to record the state after deleting.
Especially the change of subtree's height before and after adjustment.
If not, the modified will be false, then we don't need to adjust.
But if the height changed(i.e. decreased) we need to adjust. Do checking upon.
Another situation is the balanced factor of current node a is zero.
And the height of the left and right subtree is the same.
Deleting a node in one branch makes it shorter.
The height doesn't change if we modify its balanced factor.
Let's look at this example. The height of these two subtrees was h+1 before deleting.
And it was still h+1 after deleting. Because one branch didn't become shorter.
The adjustment doesn't need to pass upon in this circumstance. It can done in this level.
The second situation is that its balanced factor was not zero.
But the height of taller subtree is decreased.
Let's take a look at this example that the height of subtree was h+2 before.
Its left and right branch have the same height after deleting.
The height of this subtree became h+1.
Here We need to adjust the balanced factor of the root and set the modified to true.
Then continue passing upon and check these branches whether they need balance checking.
And another complicated situation.
The balanced factor current node a was not zero.
And the deleting happened in the shorter branch.
It became shorter after deleting.
The node a itself was unbalanced and needed to be adjusted.
The adjustment depends on the balanced factor of the heavier subtree.
Then do some adjustment.
Situation one, the balanced factor was not zero.
Take heavier right branch for example.
Left subtree is shorter. Its height decreased by one after deleting this node.
The balanced factor of heavier subtree b was zero.
Do a simple single rotation.
The height of subtree a was h+2 before deleting.
Now choose the root b of the heavier subtree as the new root.
And put a to its left subtree.
The height of both old subtree and new subtree is h+2.
So We just need to modify the balanced factor of node a and b.
The balanced factor of a was +2 before. We pulled it back and made it +1.
What about b? Its left was heavier after adjustment. And its balanced factor became -1.
The modefication was done.
Set modified to false.
Situation 3.2
node a's right was heavier and we deleted node a's left.
And the node of its right subtree was still right heavier.
Do a single rotation.
Then put the root of the heavier side as the new root.
Put node a to its left. Then let's observe these two subtrees before deleting and after deleting.
The height of the subtree, whose root is node a, was h+2.
The height of subtree b was h+1 after deleting and adjustment.
The height of the new subtree decreased by one after deleting.
And it would influent the ancestors of original node a.
Set the current node as the father of node a, then check its father.
So set modified to true.
Pass upon and keep checking.
Another situation is that the balanced factor of current node a and the root b of the heavier subtree was opposite.
Here we need to consider the root of heavier side of node b.
Set the new node c as the new root and put node a and b to its left and right side.
That is we made a double rotation.
Let's take a look at the height of these two subtrees.
The height of subtree a was h+2 before deleting.
The height of these two branches of node c could be h-1 or h-2.
But the height of one branch must be h-1. Another could be h-1 or h-2.
Because the left of node b is heavier must be guaranteed.
After deleting and adjustment.
The height of the left and right subtree of node c is h. And the height of subtree c is h+1.
Then what's the height of the subtree a and b?
That depends on the height of the left and right subtree of node c.
Then mark.
Here the height of subtree a was h+2 before.
The height of new subtree is h+1 after adjustment.
Here the adjustment need to be passed to the father of node a.
And keep checking whether the adjustment is needed.
Set modified to true. Then keep doing.
The continuous adjustment is passing upon after deleting.
If the height of the local subtree is decreased by one. Then check the upper level.
The process of passing might continue to the root if the modified is true in the root level.
It's OK because the root doesn't have a father. So we can stop here.
The process of operation depends on the height of the whole subtree.
The height of AVL tree is log n.
So the operation is log n.
Let's take a look at a example of deleting.
Look the left. Suppose that we want to delete node m.
Then find the biggest element l in its left subtree. Then replace the position of m.
It became the right picture after deleting l.
Here the current node is k after deleting node l.
The balanced factor of node k is zero before.
After one of its subtree became shorter, its balanced factor need to be modified a little bit.
But the height of subtree k didn't change. So the modefication is done.
And the deleting is done.
keep deleting node n in this tree. The current node became node l after deleting node n.
The left of node l was vertical before.
And its child k is also the same situation.
So we can use situation 3.2 to adjust.
The node l was not balanced after deleting.
Right rotation. Node k became the root of subtree and node l is its right subtree.
And node j is still hanging there.
The height of new subtree k is smaller than the original subtree l by one after deleting.
Then the information need to be passed upon to node l's father i.
And node i is also needed to be checked.
The balanced factor of node i was not zero, it was -1.
Now the right is deleted. That is the short one became shorter.
So it need a rotation to become balanced.
The balanced factor of left child was one. And it's opposite to the balanced factor of i.
The node d's right child, node g, need to join in this adjustment.
The node g was set to be the root. And node d and node i is set respectively.
The node i was root already after adjustment. The adjustment is finished.
Let's take a look at the height of AVL tree. The height is relate to the depth.
The height equal to depth + 1. Assumption: depth is K*logn.
What's K exactly?
Let's construct the most unbalanced AVL tree.
Let's look this T1 with depth one height two.
What about T2? Its left is T1. Its right is single node.
Defining this recursively can find that the most unbalanced AVL tree
Its left is Ti-1. And its right is Ti-2
Then subtree Ti of depth i is built.
We can observe that
t(1) has two nodes. t(2) has four nodes.
t(i) = t(i-1) + t(i-2) + 1 (the root)
This recursion is very similar to Fibonacci number.
that is t(i) = F(i+3)-1
We can obtain t(i) by F(i+3)-1
Closed-form expression of Fibonacci number
144
来带进去，而且呢，我们把这个t(i)呢，就用结点个数n来带进去，那就会得到i<2/3的log以2为底，括号n+1的对数再减掉1
那这是它的深度，它的高度呢，其实就是，嗯，再把这个i值呢，是再加1，也就是，3/2的log以2为底n+1的对数， http://en.wikipedia.org/wiki/Fibonacci_number
那AVL树它的检索， 插入和删除的效率都是跟它的树高有关的。 The efficiency of inserting and deleting depends on its height.
那我们前面说到它的树高和树的深度都是log以2为底n的一个对数， The height and depth is logn.
那因此呢，具有n个结点的AVL树，它的插入删除，和检索的一个效率呢都是log n的量级。 So efficiency of indexing is logn.
AVL树呢，它比较适合组织内存里面小规模的数据 AVL tree is very fit to the small scale data in memory。
对于大规模的数据呢，我们就把它导到外层用B树和B+树来组织， For large scale data, we can use B tree or B+ tree with external memory.
那如果是内存能够放下，而且这个数据规模呢，还是特别大，那一般情况下，我们也是在内存里面用B树来组织的。 For large data in memory, we usually use B tree.
另外呢，就是AVL树，啊，它的这个插入删除的维护代价还是比较大的， Beside the inserting and deleting of AVL tree takes a big price.
所以现在呢，已经不是特别常用，那我们很多情况下是用红黑树，或者splay tree来替代。 So in most circumstances, we use red-black tree of splay tree instead.
那最后给大家一些思考，就是我们对比一下红黑树，还有AVL树，大家看一下它们的这个树高有些什么样的差异 Let's think about this. What's the difference of the height of red-black tree and AVL tree.
另外呢就是在它的结点插入删除的操作上，我们有哪一些相似的地方，有哪些不同， And the similar of inserting and deleting between these two trees.
还有我们考虑下这个代码它们的易写性和可维护性，哪一个是更好一些 And the difficulty of writing codes.
特别是我们还要考虑一下，在统计意义上，也就是说，我们在实际运行过程中，到底是红黑树的效率更高，还是AVL树的效率更高。 Efficiency between these two trees.
谢谢大家。 Thank you.