스니스니 닷넷

1. tinyos-1.1.11-3is.exe 설치.
2. 패치
tinyos-1.1.12Apr2005cvs-1.cygwin.noarch.rpm
tinyos-1.1.13May2005cvs-1.cygwin.noarch.rpm
끝.

소스 코드를 찾아보자.
(헤매다가, 준상 슨배가 찾아줬다ㅡ 하하하; )
opt\tinyos-1.x\tos\platform\micaz 에 있다.

nesC를 잘 분석해보자. 하하하

내게 플립플랍은 논리회로이다. 그런데, 보니까 끈쌘달을 플립플랍이라고 부르는 것이다. 그래서 찾아봤다.

flip-flop〔│〕 n.
1 《미·구어》 (동향·소신·태도·방침 등의) 급변, 전환
do a flip-flop 급하게 변경하다
2 역공중제비
3 퍼덕퍼덕하는 소리
4 [pl.] 고무 슬리퍼[샌들]
5【전자】 플립플롭 회로(= crcuit) 《교호(交互) 접속식 회로》
━ vi. (~ped;~·ping) 퍼덕퍼덕[덜컥덜컥]하다;역공중제비를 하다;달각달각 움직이다
━ ad. 퍼덕퍼덕하며, 덜컥덜컥하며



sequential logic은 현재 입력+상태로 출력값이 정해진다.
따라서, sequential logic은 회로 내부에 값(상태)들을 기억하기 위한 메모리 소자들을 가지게 되며, 일반적으로 많이 사용되는 메모리 소자가 flip-flop이다.

플립플랍은 1비트의 정보(0또는1)를 저장할 수 있는 메모리 소자이며,
논리 게이트들을 연결하는 방법에 따라 latch, SR/JK/D/T(제어신호와 클럭신호를 입력으로 갖는다.) 플리플랍이 있다.

파일 이름을 인자로 sys_open()이 호출 되면 파일 시스템은 요청된 파일에 대한 inode를 찾는다.

1. sys_open()
http://lxr.linux.no/source/fs/open.c?v=2.4.28#L798
798 asmlinkage long sys_open(const char * filename, int flags, int mode)
799 {
800 char * tmp;
801 int fd, error;

808 if (!IS_ERR(tmp)) {
809 fd = get_unused_fd();
810 if (fd >= 0) {
811 struct file *f = filp_open(tmp, flags, mode);
812 error = PTR_ERR(f);
813 if (IS_ERR(f))
814 goto out_error;
815 fd_install(fd, f);
816 }

826 }

2. filp_open() : open_namei()가 찾아준 inode를 찾아주면, struct file을 위한 메모리 공간을 할당하고 이 구조의 초기화를 수행한다.
http://lxr.linux.no/source/fs/open.c?v=2.4.28#L656
656 struct file *filp_open(const char * filename, int flags, int mode)
657 {
658 int namei_flags, error;
659 struct nameidata nd;
660

667 error = open_namei(filename, namei_flags, mode, &nd);668 if (!error)
669 return dentry_open(nd.dentry, nd.mnt, flags);
//오잉? nd는 선언만 하고, inode 찾아오라고 open_namei()에 보내는데,
//open_namei()1018번째 줄은 뭐하는 짓이란 말인가!
672 }

(*)nameidata의 자료구조는 다음과 같다.
http://lxr.linux.no/source/include/linux/fs.h?v=2.4.28#L697
697 struct nameidata {
698 struct dentry *dentry;
699 struct vfsmount *mnt;
700 struct qstr last;
701 unsigned int flags;
702 int last_type;
703 };


3. open_namei() : 인자로 전달된 파일 이름과 디렉토리 구조를 이용해 그 파일에 대응되는 inode를 파일 시스템에서 찾아 리턴한다.
http://lxr.linux.no/source/fs/namei.c?v=2.4.28#L1001
1001 int open_namei(const char * pathname, int flag, int mode, struct nameidata *nd)
1002 {
1003 int acc_mode, error = 0;
1004 struct inode *inode;
1005 struct dentry *dentry;
1006 struct dentry *dir;
1007 int count = 0;
1008
1009 acc_mode = ACC_MODE(flag);
1010
1011 /*
1012 * The simplest case - just a plain lookup.
1013 */
1014 if (!(flag & O_CREAT)) {
1015 error = path_lookup(pathname, lookup_flags(flag), nd); //옹.. 여기서 dentry 찾아 넣어주나? ( '')
1016 if (error)
1017 return error;
1018 dentry = nd->dentry; // 문제의 1018
1019 goto ok;
1020 }
1021
1022 /*
1023 * Create - we need to know the parent.
1024 */
1025 error = path_lookup(pathname, LOOKUP_PARENT, nd);
1026 if (error)
1027 return error;

4. path_lookup() : path를 찾아주나 보다.
http://lxr.linux.no/source/fs/namei.c?v=2.4.28#L744
744 int fastcall path_lookup(const char *path, unsigned flags, struct nameidata *nd)
745 {
746 int error = 0;
747 if (path_init(path, flags, nd))
748 error = path_walk(path, nd);
749 return error;
750 }

우어어ㅡ 이렇게 막 따라가다 보므는... 끝이 음따.. 리눅스... OTL

5. path_init() : path를 초기화 해주나 보지... (의욕 상실 중.)
http://lxr.linux.no/source/fs/namei.c?v=2.4.28#L754
754 int fastcall path_init(const char *name, unsigned int flags, struct nameidata *nd)
755 {
756 nd->last_type = LAST_ROOT; /* if there are only slashes... */
757 nd->flags = flags;
758 if (*name=='/')
759 return walk_init_root(name,nd); // 따라갔더니 특별한 것 없음.
760 read_lock(¤t->fs->lock);
761 nd->mnt = mntget(current->fs->pwdmnt);
762 nd->dentry = dget(current->fs->pwd); // 이야ㅡ 드디어 덴트리 받아오는 진짜 함수를 발견! -ㅇ- 알고보니 pwd -ㅇ-;;;;
763 read_unlock(¤t->fs->lock);
764 return 1;
765 }

6. path_walk() : link_path_walk()를 부른다.
http://lxr.linux.no/source/fs/namei.c?v=2.4.28#L656

7. link_path_walk() : 오오ㅡ 뭔가 내가 찾던 바로 그 함수인 듯 -ㅇ- (기대기대~)
http://lxr.linux.no/source/fs/namei.c?v=2.4.28#L450
450 int fastcall link_path_walk(const char * name, struct nameidata *nd)
451 {
452 struct dentry *dentry;
453 struct inode *inode;
454 int err;
455 unsigned int lookup_flags = nd->flags;
456
457 while (*name=='/')
458 name++;
459 if (!*name)
460 goto return_reval;
461
462 inode = nd->dentry->d_inode;
// 허걱!! dget() 함수에소 inode를 가져온건가ㅡ 왜 이까지 왔지 -ㅇ-

8. dget()
244 static __inline__ struct dentry * dget(struct dentry *dentry)
245 {
246 if (dentry) {
247 if (!atomic_read(&dentry->d_count))
248 out_of_line_bug();
249 atomic_inc(&dentry->d_count);
250 }
251 return dentry;
252 }

모르겠다. 잠온다. -.-

하드 디스크를 컨트롤하는 아주 쉬운 방법 중에 하나이다.

온라인 상에서 hdparm을 다운 받아서 그냥 깔아만 주면 된다.

http://www.ibiblio.org/pub/Linux/system/hardware/

요기에서, hdparm 최신 버젼을 받는다.

나는 hdparm-5.9.tar.gz을 다운 받았다.

]# tar xzf hdparm-5.9.tar.gz
으로 압축을 풀어서, hdparm-5.9 폴더에 들어가보자.
뭔가가 많다. (사실 이정도는 많은 편은 아니지만)

그리고 그냥 실행하면 된다..;;

]# hdparm -M /dev/hda : 라고 하면, 이 하드가 acoustic setting을 지원하는 지 알 수 있다. 이건 잘 모르겠지만, 하드 스핀 속도를 조절하는 것 같은데, 128~256 값이 있고, 128이 가장 느리고 조용한 상태이고, 256은 가장 빠르지만 시끄러운 상태이다.
내 도시바 R100에서는 작동하지 않는다.

그리고 많이 사용하는 것은,
]# hdparm -y /dev/hda : 이건, standby 상태로, 하드 스핀 속도를 낮추어 놓고 있다가, 어떤 작업이 들어오면 다시 하드가 열심히 돌아간다.
실제로 이걸 써 보면, 하드가 퓽~ 꺼졌다가, 일을 시키면 다시 "이융~~" 하고 돌아가는 것을 들을 수 있다. (조용한 곳에서.)

]# hdparm -Y /dev/hda : 이것은, sleep 상태로, 하드를 잠재운다.. ( '') 그래서 이건 일을 시켜도 안되고, 가서 깨워야 하는데, (hard reset) 내가 못찾은건지는 모르겠는데.... hdparm 에는 하드 리셋 옵션을 찾을 수 없었다. 다행히, 리눅스에서 ACPI를 지원하므로,
내가 일을 시키면 ACPI가 열심히 애를 깨운다. 엄청 늦게 일어난다. (요 ioctl 을 찾아봐야겠다.)

]# hdparm -S 1 /dev/hda : 이것은, 아무 일 없이 1(5초)간 있으면, (idle 상태) 하드를 standby 상태로 만들라는 것. 5초로 설정해 놓으면, 정말, 얘가 계속 혼자 핑~ 이융~ 핑~ 이융~ 하는 것을 들을 수 있다. -_-;;; (오ㅡ 내 베터리~~~ )

]# hdparm -C /dev/hda : 요거는 지금 하드의 상태를 알아보는 것인데.... 이거 실행 시키면 스탠바이 하던 하드도 일어나고, 자고 있던 하드도 일어난다;;;

]# hdparm -w /dev/hda : 요거는 하드 리셋 시키는 건데...
옵션 설명에 (dangerous)라고 적혀있다. 근데 해봤다. 내 노트북에서는 ACPI가 자는 하드를 깨우지만, 그렇지 않다면 시스템을 리붓시킬 수 밖에 없기 때문에, reset 시키는 ioctl 을 call 하는 거 같길래..
함 해봤더니... ( '') 시스템이 뻗었다. 하하하하
(세그멘테이션 오류가 났다. 잘못된 메모리를 참조한 거란다.)

소스 코드가 보고 싶다면, hdparm.c 파일을 보고 열심히 잘 trace 해보면 된다.

hdparm.c
main(int argc, char **argv)
{
...
case 'y';
get_standbynow = noisy;
noisy = 1;
set_standbynow = 1;
break;
case 'Y';
get_sleepnow = noisy;
noisy = 1;
set_sleepnow = 1;
break;
...
process_dev(*p); // *p is device name such as /dev/hda
}

void process_dev (char *devname)
{
int fd=open(devname, open_flag);
...

if (set_sleepnow) {
unsigned char args1[4] = {WIN_SLEEPNOW1,0,0,0}; //#define WIN_SLEEPNOW1 0xE6
unsigned char args2[4] = {WIN_SLEEPNOW2,0,0,0}; //#define WIN_SLEEPNOW2 0x99
if (get_sleepnow)
printf(" issuing sleep command\n");
if (ioctl(fd, HDIO_DRIVE_CMD, &args1)
&& ioctl(fd, HDIO_DRIVE_CMD, &args2))
perror(" HDIO_DRIVE_CMD(sleep) failed");
}

if (set_standby) {
unsigned char args[4] = {WIN_SETIDLE1,standby_requested,0,0};
if (get_standby) {
printf(" setting standby to %lu", standby_requested);
interpret_standby(standby_requested);
}
if (ioctl(fd, HDIO_DRIVE_CMD, &args))
perror(" HDIO_DRIVE_CMD(setidle1) failed");
}
...
}

자ㅡ 그러면 저 ioctl()은 어디에 있는가?
헤더는, "/usr/include/sys/ioctl.h" 에 있다.

그리고, 이... 하드의 드라이버를 찾아가보자ㅡ
/usr/src/linux-2.6.9/drivers/ide/
1. Find "HDIO_DRIVE_CMD" : ide.c
int generic_ide_ioctl(struct file *file, struct block_device *bdev, unsigned int cmd, unsigned long arg)
{…
switch (cmd) {
...
case HDIO_DRIVE_CMD:
if (!capable(CAP_SYS_RAWIO))
return -EACCES;
return ide_cmd_ioctl(drive, cmd, arg);
...
}
}
EXPORT_SYMBOL(generic_ide_ioctl); // 요건 밖에서도 이 함수 사용할 수 있도록 끄집어 내 놓은것.

#### 아~ 여기서 부터는 trace를 하긴 했는데, 잘 모르겠네. 호호호호~~ =33
ide-taskfile.c
1. ide_cmd_ioctl( )
2. ide_wait_cmd( )

ide-io.c
ide_do_drive_cmd( )
{
blk_put_request(rq); // driver/block/ll_rw-blk.c
}

[sample program 1]
# program reads integers and adds them in the loop,
# it stops when 0 is read, printing out the sum at that point

main: # begin of assembly program consisting only of text segment
li $a0, 0 # pseudoinstruction: move immediate to dest
loop:
li $v0, 5 # system call read integer code in $v0
syscall # system call: feature of SPIM, not MIPS
add $a0, $a0, $v0 # in $v0 read integer
bne $v0, $zero, loop # if not 0 back to loop
li $v0, 1 # print integer system code to $v0
syscall # proper printing
li $v0, 10 # exit program system code in $v0
syscall # exit program

[sample program 2]
.text # begin of code
.globl __start

__start:

li $a0, 0 # $a0라는 아큐먼트레지스터에 constant값 0을 대입합니다.
loop:
li $v0, 5 # $v0는 시스템이 어떤 일을 할지 정해주는 레지스터입니다. 여기서 5라 함은 시스템이 입력값을 받을수 있도록 기다리라는 뜻입니다.

syscall #이것은 spim 문법으로 이것이 호출되면 $v0에 있는 내용에 따라 시스템이 작동합니다.
add $a0, $a0, $v0 # 어떤 입력값이 들어오면 그것을 $a0에 더합니다. (여기서 $v0는 시스템의 입력값을 가지는 리턴값이라고 생각하시면 됩니다)
bne $v0, $zero, loop # 만약 들어온 값이 숫자이면 계속 loop로 가서 루프를 돕니다.

li $v0, 1 #숫자가 아니거나 숫자 0이면 $v0를 1로 셋팅함으로서 print integer 명령을 주고

syscall # 실행합니다. 이 때 화면에 찍히는 값은 $a0에 있는 값입니다.
li $v0, 10 # $v0를 10으로 셋팅함으로써 종료 명령을 셋팅하고
syscall # 실행시킴으로써 프로그램을 종료합니다.


[sample program 3]
# C program
# #include
# main()
# {
# int i;
# int sum=0;
# for (i=0; i<=100; i=i+1) sum=sum + i*i;
# printf("The sum from 0 .. 100 is %d\n",sum);
# }

.text # 프로그램시작
.align 2 # 1word를 2bytes로 셋팅
.globl main # main함수 선언
main:
li $t0,0 # clear $t0 - i=0
li $t2,0 # clear sum
loop:
mul $t1,$t0,$t0 # i * i
addu $t2,$t2,$t1 # calculate new sum
addi $t0,$t0,1 # i = i + 1
ble $t0,100,loop # if i<=100 return to loop

la $a0,str # address of string to print in $a0
li $v0,4 # system call code for print_str SPIM i/o call
syscall

move $a0,$t2 # pseudoinstr: move result to $a0
li $v0,1 # system call code for print_int
syscall

jr $ra # end of program, return to system

.data # put this to data segment
str: # string for printing
.asciiz "The sum from 0 .. 100 is "

[sample program 4]
# 10! 구하는 프로그램~
#
# main ()
# {
# printf("The factorial of 10 is %d\n",fact(10));
# }
#
# int fact(int n)
# {
# if (n<1)
# return(1);
# else
# return(n*fact(n-1));
# }
　
.text # put code into text segment
.globl __start # declare label main global
# to be accessible from other files
__start:
subu $sp,$sp,32 # stack frame is 32 bytes long,
# min length 24
# here we use it to store only
# $fp, $ra, and $a0
sw $fp,16($sp) # save old frame pointer, after $a0-$a3
sw $ra,20($sp) # save return address in $ra
addu $fp,$sp,28 # set up frame pointer to the 1st word in frame

li $a0,10 # put argument (10) for factorial
jal fact # call factorial function

move $s0,$v0 # store result from $v0 to avoid destruction
la $a0,$LC # put string address in $a0
li $v0,4 # system call code for print_str
syscall

move $a0,$s0 # pseudoinstr: move result to $a1
li $v0,1 # system call code for print_int
syscall

lw $ra,20($sp) # restore return address
lw $fp,16($sp) # restore frame pointer
addu $sp,$sp,32 # pop stack frame - clean frame
jr $ra # end of program, return to system

.rdata # put this to data segment
$LC: # string for printing
.asciiz "The factorial of 10 is \n"

.text # again text segment
fact: # keeps code for factorial
subu $sp,$sp,32 # same thing with frame preparation
sw $ra,20($sp)
sw $fp,16($sp)
addu $fp,$sp,28
sw $a0,0($fp) # save factorial argument (n)

lw $v0,0($fp) # load n - kept in $a0 saved on stack
bgtz $v0,$L2 # branch if n>0
li $v0,1 # return 1 (0!=1)
j $L1 # jump to code to return

$L2:
lw $v1,0($fp) # load n
subu $v0,$v1,1 # compute n-1
move $a0,$v0 # move value to $a0
jal fact # call recursively factorial function

lw $v1,0($fp) # load n, here in fact proper computation of factorial
mul $v0,$v0,$v1 # computer fact(n-1) * n, note that $v0 is preserved
# it multiplies successive values from $a0 stored in frames

$L1: # result is in $v0
lw $ra,20($sp) # restore $ra
lw $fp,16($sp) # restore $fp
addu $sp,$sp,32 # pop stack
j $ra # return to caller

우선은...
윈도우즈에서, 아무 생각 없이 파티션을 날렸는데,
GRUB를 날리지 않았을 때...
윈도우로 부팅하는 방법.
grub> rootnoverify (hd0,0)
grub> makeactive grub
grub> chainloader +1
grub> boot

grub는 이래저래 장점이 많으나,
덩치도 크고, 플로피와 씨디롬 부팅이 안된다!!는 것을 유념해야한다.

그리고.
분명! FedoraCore3 설치시에는 "커널개발"이 없다! T.T
그래서 나는 다시 커널 소스를 다운 받아서 깔아줘야했다.
사실, 익숙한 사람들에겐 정말 별 것 아닌 일이지만.

난 분명 저번주에 깔았음에도 까먹은 것으로 보아, 적어놔야겠다. -_-;;

1. 소스를 다운 받는다;
2. rpm -ivh kernel-2.6.9-1.677.src.rpm
-> /usr/src/redhot/SOURCE 에 깔린다.
3. /usr/src/redhot/SOURCE 에 가서. 타볼소스를 풀어준다.
bunzip2 linux-2.6.9.tar.gz2
tar xvf linux-2.6.9.tar -C /usr/src

끝! 간단하고나..

==========================================================
자. 이제 컴파일을 해보자! -ㅇ-

우선 그 전에 해줘야 할 것이 있다.
버젼이 디리리리 바뀌어도 일관성 있게 편리하게 사용할 수 있도록,
"linux" 라는 심볼릭 링크를 걸어주자!

/usr/src/에서 ]$ ln -sf linux-2.4.22 linux
이렇게 하면, linux-2.4.22폴더를 linux 라고 지칭할 수 있다. 확인!
/usr/src/에서 ]$ ls -al
"~~~~ linux -> linux2.4.22 " 을 볼 수 있을 것이다.
그리고 심볼릭 링크를 하나 더 걸어줘야 하는데, 바로 asm 이다.
/usr/src/linux에서 ]$ ln -sf asm-i386 asm

자. 그러면, 컴파일 해 볼까요?
/usr/src/linux 폴더 아래에서 해야한다.
1. ]$ make mrprop : 이전의 config 무시하고 다시 설정할 때. 기존의 config 에서 몇 개 추가해주는 거 정도에선 안해도 된다.

2. ]$ make menuconfig : 여기에서 이제 뺄 것 빼고 더할 것 더하면 된다. <*> 표시는 커널에 넣을 것, 표시는 모듈로 만들 것, < >는 선택 안함.

2-1. 다른 .config 파일을 불러서 할 수도 있고, 다른 .config 파일을 linux 폴더 안에 쓱~ 넣어 놓고, ]$make oldconfig 하면서 선택 삭제 해 주어도 된다. 주로, [N/y/?] 라고 물어보는데, 대문자가 디폴트. ?는 설명.

3. ]$ make dep : 이제 설정해 주었으니, 디펜던시를 잡아준다.

4. ]$ make clean :

5. ]$ make bzImage :

6. ]$ make install

7. ]$ make modules :

8. ]$ make modules_install :

ACPI [Advanced Configuration and Power Interface]

1996년에 인텔(Intel)과 마이크로소프트(Microsoft), 일본의 도시바(東芝)가 공동으로 작업하여 책정한 컴퓨터의 전원 관리 규격.

요약
1996년에 인텔(Intel)과 마이크로소프트(Microsoft), 일본의 도시바(東芝)가 공동으로 작업하여 책정한 컴퓨터의 전원 관리 규격.

오퍼레이팅 시스템에 의해 프로세스는 물론, 컴퓨터에 접속한 각종의 주변 회로, 기기류의 전원 상태 등을 세밀하게 조정할 수 있다.

기존에는 하드웨어에 가까운 부분에서 APM이라는 규격이 절전 기능을 실행하고 있었지만, 앞으로는 ACPI 규격에 의한 제어로 차츰 바뀔 것으로 기대된다. 데스크탑 컴퓨터에서도 이 규격을 사용함으로써, 노트형퍼스컴(노트북)과 같은 서스팬드(suspend:작업 실시 중에 일시적으로 정지하는 것)와 그 복귀에 의해 더욱 빠르게 기동할 수 있다.

서스팬드 중에는 냉각팬의 소음을 포함해 컴퓨터는 어떤 소음도 내지 않기 때문에 가정용 컴퓨터에서도 환영받을 것으로 전망된다. 물론 서스팬드 중이라도 팩스 모뎀에 착신 신호가 들어오면 바로 응답하여 대응한다.

단지 ACPI를 처음으로 적용한 운영 체제는 윈도98이고, 제품의 대응 상황에 관해서는 아직은 안정적이지 않다. 현재의 상태에서는 노트북의 절전 기능에 있어서는 APM을 사용하는 편이 효율이 있다는 사례도 있고, 업계 표준으로 자리잡기까지는 아직 시간이 걸릴 것으로 보인다.

1. vs로 창을 수직 분할한다. (수평 분할은 hs인듯 했으나, 모르겠다.)
2. 창 간의 이동은, Ctrl+w 을 누른 상태에서, j, k, h, l을 누르면 된다.
3. 전체 선택은, 명령행에, 1,$ y 하면 된다.
($는 마지막을 뜻한다. 창 안에서는, 그 줄의 끝을 뜻한다.)
4. v: char 단위 선택
Shift+v: line 단위 선택
Ctrl+v: column 단위 선택
5. Ctrl+W+I : C 코딩할 때,스트럭쳐나 함수 선언 찾아가는 것.
6. :e 파일이름 : 에디트.

므히히ㅡ 지금은 학교 앞, 로시망고. (레드망고 짝퉁)
보리 슨배 노트북으로!
선배가 네스팟 뚫어줬다. 므히히히히.
어떻게 하는지 볼랬는데.. 보고 있자니 머리가 너무 아파서... ( '')

이건 지난 학기 FS 시간에 배운 것인데,
이번에 알고리즘 시간에 나와서
한 번 복습!



⊙ Introduction
여기에서 다루는 kd-tree는 공간 DB로, 기존의 문자 DB와는 다르다. key 값 매칭 문제이고, 굉장히 큰 양을 공간 기반으로 검색한다. 공간 기반 검색이란, range로 표현된 질의를 검색한다는 것이다. Spatial data는 points, lines, polygons 등을 포함하고 있따.
Spatial data를 효율적으로 지원하기 위해서는, 다음과 같은 특징적 어려움을 알아야 한다.
① First, spatial data are latge in quantity, complex in structures and relationships
② Second, the retrieval process employs complex spatial operators like intersection, adjacency, and containment
③ Third, it is difficult to define a spatial ordering, so conventional techniques cannot be employed for spatial operations
→ spatial indices 필요!

(1) kd-tree : Binary-tree based indexing
kd-tree는 multi-attribute data index를 binary search하는 tree로, k는 표현될 데이터 공간의 차원을 가리킨다. 각 depth에서, 어떤 branch로 갈 것인가를 결정하는 데에 다른 attribute이 사용된다. 예를 들어, 2-d (x,y) tree에서는 짝수 depth에서 x 좌표가 branch 기준이라면, 홀수 depth에서는 y 좌표가 branch 방향의 기준이 된다. 마지막으로, 이 tree는 꼭 균형을 이룰 필요는 없다.

A가 제일 먼저 들어간 것을 알 수 있다. 즉, 최초의 분리자는 root이다.

① Principle
Node는 각각의 실제 data point를 나타내고, 검색 방향의 지표가 된다. (left, right 두 개의 child가 있다.→ 현재 노드 값 보다 작은가? 큰가?)
한 Node는 5개의 field로 구성되어 있다. LOSON(작은 값을 가진 left 자식), HISON(큰 값을 가진 right 자식), 좌표(x,y,...), NAME(해당 노드에 대한 정보. 포인터가 들어갈 수도 있다.), DISC(좌표 이름을 가리킨다. 즉, 이 노드는 x를 기준으로 했느냐 y를 기준으로 했느냐. 등. ).

② Insertion
Binary search tree에서의 insertion 방법과 유사하다. 다른 점이 있다면, 앞에서 설명 했듯이, depth마다 비교하는 attribute가 다르다는 것이다. tree의 bottom에 도달하면, 거기에 새 node를 넣는다.

매우 쉽다;

③ Search
Search 역시 매우 straightforward하다. 흐흐 BST 처럼 찾아 내려가면 된다. 여기에서 역시, 다른점은 depth마다 비교 기준의 attribute이 다르다는 점 뿐. 참 그리고, 질의가, 조건 질의가 가능하다는 것이 또 하나 틀린데, 예를 들어, 'Y>20인 점들을 찾아라' 라든지, '(75,15)에 가까운 점들을 찾아라' 등이 가능하다는 것이다.
Region Search는 Euclidean distance를 이용하여 구할 수있다. node (a,b) 근처 거리 d안에 있는 점들을 다 구하라는 질의가 들어오면, 우선 (a-d) ≤ x ≤ (a+d), (b-d) ≤ y ≤ (b+d) 안의 점들을 다 구한다. 그런데 이렇게 구한 점은, 반지름 d인 원 안에 있는 점이 아니라, 한 변이 2d인 정사각형 안에 들어오는 점이므로, 점들을 구한 다음에 range안에 들어오는 게 맞는지 확인이 필요하다.

Search 결과 Miami를 찾았다!

④ Deletion
앞에 insert나 search는 BST와 비슷하여 쉬웠지만, deletion은 좀 더 복잡하다. 각 depth마다, DISC가 달라서, 원래 tree의 root는 DISC가 x 지만, subtree의 root는 y가 될 수도 있기 때문에, 모든 subtree가 kd-tree가 아니다. 그래서 그냥 마구 삭제해 버리면 문제가 생긴다.
kd-tree로 부터 (a,b) 노드를 삭제한다고 할 때, (a,b)의 두 subtree가 empty tree이면 그냥 삭제하면 되고, 아니면 (a,b)의 subtree들 중에서 가장 적절한 대체 노드 (c,d)를 찾아서, replace시킨다. 이 (c,d)는 recursive하게 다시 삭제되는 것이다. 그렇다면, 이 대체 노드는 어떻게 찾는 것일까? 오른쪽 subtree에서 가장 작은 값을 가진 노드나, 왼쪽 subtree에서 가장 큰 값을 고르면 된다. 그러면 다음의 예를 보자.

사실 이것도 찬찬히 보면 매우 쉽다. 그죠?

⑤ 장단점
kd-tree는 partial matching search에 유용하지만, empty space가 없고, point search와 region search가 다 가능하다. 하지만, 균형이 심~하게 안맞으면 performance가 안좋다. kd-tree는 메모리 기반 index이다. File 기반에서는... 안좋다.

9.3 Text Compression
Text compression은 low-bandwidth channel 이나 fixed-capacity storage device 등에서 중요한 문제이다. ASCII(16bits)나 Unicode system(16bits)에서는 fixed length binary string을 사용하는데 반해, Huffman code는 frequency가 클 수록 더 짧은 길이의 code를 부여하는 variable length encoding 방법을 사용하여 space를 줄인다.
이런 variable length code를 사용하기 위해서는, 이것은 prefix code여야한다. Prefix code란, 'no code word in our encoding is a prefix of another code word in its encoding'이다. 사실, 뜻은 prefix-free code이다. 이 때문에 code word 길이는 길어질 수 있지만, 그래도 fixed length를 사용하는 것 보다는 공간이 절약된다. 특히나, 인간이 사용하는 언어와 같이 frequency들 간의 차이가 큰 경우 더욱 효율적이다.

1) The Huffman Coding Algorithm
⊙ Huffman tree 만들기
root를 single-binary tree로 시작하여, frequency가 낮은 것부터 merge한다.

d개의 distinct char가 있고, text 길이가 n이라 하면, 두 binary tree를 merge하는 while-loop 동작은 d-1번 수행되고, priority queue 유지하는데 O(logd)걸리므로, 이 Huffman tree를 만드는 데 걸리는 시간은 O(n + dlogd)가 된다.

2)The Greedy Method Revisited
Huffman's Algorithm은 일종의 Greedy method이다. ...