pashka's blog

ITMO Algorithms Course. Semester 2. Lecture 5
By pashka, history, 4 years ago, In English

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!

  • Vote: I like it
  • +28
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It indeed only makes sense to put $$$\alpha < 1$$$, but then the property works, and makes the height of the tree O(log(n))

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yep makes sense It seems that there should be a typeo.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply