Anki Deck Changes

Commit: 3415db96 - fix 2-3 tree insertion

Author: obrhubr <obrhubr@gmail.com>

Date: 2026-01-09T14:16:17+01:00

Changes: 2 note(s) changed (1 added, 1 modified, 0 deleted)

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Cloze
GUID: H?Cs9sT6&{
modified

Before

Front

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees
2-3 Tree: Insertion steps:
  1. Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
  2. Insert the new key value as a separator
  3. Rebalance (if necessary, i.e. more than 3 keys)
  • split node into two nodes (each gets 2 children and 1 seps)
  • the middle sep is pushed to the parent level (and propagate)

Back

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees
2-3 Tree: Insertion steps:
  1. Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
  2. Insert the new key value as a separator
  3. Rebalance (if necessary, i.e. more than 3 keys)
  • split node into two nodes (each gets 2 children and 1 seps)
  • the middle sep is pushed to the parent level (and propagate)
The rebalancing being recursively pushed to the parent limits the operations at the height \(h\) thus we get \(O(\log n)\).

After

Front

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees
2-3 Tree: Insertion steps:
  1. Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
  2. Insert the new key value (or that of another child, as works) as a separator
  3. Rebalance (if necessary, i.e. more than 3 keys)
  • split node into two nodes (each gets 2 children and 1 seps)
  • the middle sep is pushed to the parent level (and propagate)

Back

ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees
2-3 Tree: Insertion steps:
  1. Search for the correct node under which the key is inserted: \(O(\log_2 n)\)
  2. Insert the new key value (or that of another child, as works) as a separator
  3. Rebalance (if necessary, i.e. more than 3 keys)
  • split node into two nodes (each gets 2 children and 1 seps)
  • the middle sep is pushed to the parent level (and propagate)
The rebalancing being recursively pushed to the parent limits the operations at the height \(h\) thus we get \(O(\log n)\).
Field-by-field Comparison
Field Before After
Text <b>2-3 Tree</b>: Insertion steps:<br><ol><li>{{c1::Search for the correct node under which the key is inserted:&nbsp;\(O(\log_2 n)\)}}</li><li>{{c2::Insert the new key value as a&nbsp;<b>separator</b>}}</li><li>{{c3::<b>Rebalance</b>&nbsp;(if necessary, i.e. more than 3 keys)<br></li></ol><ul><li>split node into two nodes (each gets 2 children and 1 seps)</li><li>the middle sep is pushed to the parent level (and propagate)}}</li></ul> <b>2-3 Tree</b>: Insertion steps:<br><ol><li>{{c1::Search for the correct node under which the key is inserted:&nbsp;\(O(\log_2 n)\)}}</li><li>{{c2::Insert the new key value (or that of another child, as works) as a&nbsp;<b>separator</b>}}</li><li>{{c3::<b>Rebalance</b>&nbsp;(if necessary, i.e. more than 3 keys)<br></li></ol><ul><li>split node into two nodes (each gets 2 children and 1 seps)</li><li>the middle sep is pushed to the parent level (and propagate)}}</li></ul>
Tags: ETH::1._Semester::A&D::05._Data_Structures::2._ADT_Dictionary::2._2-3_Trees

Note 2: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: qx(`A-^(T{
added

Previous

Note did not exist

New Note

Front

ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::3._Relations::6._Special_Properties_of_Relations
Definition of irreflexive

Back

ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::3._Relations::6._Special_Properties_of_Relations
Definition of irreflexive
A relation \(\rho\) on a set A is called irreflexive if \(a \ \not \rho \ a\) for all a ∈ A, i.e., if \(\rho \ \cap \ \text{id} = \emptyset\).

Not that this is not the negation of reflexive!
Field-by-field Comparison
Field Before After
Front Definition of irreflexive
Back A relation&nbsp;\(\rho\)&nbsp;on a set A is called <b>irreflexive</b> if&nbsp;\(a \ \not \rho \ a\)&nbsp;for all a ∈ A, i.e., if&nbsp;\(\rho \ \cap \ \text{id} = \emptyset\).<br><br>Not that this is not the negation of reflexive!
Tags: ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::3._Relations::6._Special_Properties_of_Relations
↑ Top