How a creative bug maker makes creative bugs -->
2020 Winter Break Plan
Jan 28, 2020 12:56 PM
No Excerpt
plan
AVL
Apr 19, 2019 2:56 PM

Intro

AVL is a great data structure, which get rid of the disadvantage of ordinary BST. As we all know, for BST, when the data is bad enough, it's very likely become a linked list, which will make the time complexity very bad $O(n)$ The rotation of AVL can prevent us from this problem.

Concept

Height: NULL? -1 : max{height(leftchild), height(rightchild}+1 Balance: $|height(left)-height(right)|$ If balance factor is greater than 1, we say this tree is unbalanced.

Programming
B-Tree
Apr 19, 2019 2:55 PM

Intro

Why BTree?

Since the speed to access memory is much more faster than the speed to access disk, therefore, we need a data structure to make the height as small as possible.

The hard disk support to load a chunk of data in one time

Defination

order: the number of children of each node, or 1+max number of element of each node

Find

Find is easy, we need only find the right interval through root to the leaf. Also one property the BTree has is that for each chunk of data if one node, it's sorted. So we can use binary search to do it.

Programming
Making a 0-backend blog system
Jan 17, 2020 10:32 PM
No Excerpt
Blog
Something need to be covered
Jan 28, 2020 5:00 AM
No Excerpt
Constructor
Jan 28, 2020 5:00 AM
No Excerpt
Header File
Jan 28, 2020 5:00 AM
No Excerpt
auto
Jan 28, 2020 5:00 AM
No Excerpt
  • ...
Copyright © 2015-2020   Laphets. All Rights Reserved.