| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 155 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
Here is the video of the lecture. Thanks to everyone who watched the live stream.
Last week I forgot to make the home tasks, please send me the message if this happens again.
Here are the home tasks for the lecture, you can submit your solutions into this form.
See you next week!
Hey, I am now at the last exercise. Shouldn't the definition of weight balanced be the other way: So $$$w(v) \leq floor(\alpha w(parent(v))$$$? Because now a BST that is a linked list (only right children) also fits the definition when $$$\alpha = 0.5$$$, and that has clearly height O(n)
But what you said also doesn't make sense since if we put $$$\alpha=1$$$ the not only the path graph but any random tree will satisfy the condition :)
It indeed only makes sense to put $$$\alpha < 1$$$, but then the property works, and makes the height of the tree O(log(n))
Yep makes sense It seems that there should be a typeo.
I tried to implement AVL tree using the tricks in the video but I got into some problems.I used to store then nodes in a vector so that I can add any when needed but when I want to delete a node I need to have linear time to delete it I can use a set but it doesn't make sense and I can just ignore deleted nodes but that consumes a lot of memory.Can anyone help me?
What you could do for delete, is swap the node you want to delete with the last node in the vector. Than update all relevant pointers for this node that now has a different location, and finally you use vector.pop_back(). This makes the delete O(log(n)) + O(1) again. I think for this it is easier to have parent pointers. Unfortunately, this will make the indexes that point to a BST Node no longer permanent, because it could swap positions.