The Study Note Written by JeaYoung

class Node
  attr_accessor :keys, :parent

  def initialize (p, key)
    # keys = [P0, K1 ,P1, K2, ...., Pn ]
    if key.class == Array
      @keys = key
    else
    @keys = [nil,key,nil]
  end
    @parent = p
  end   # end of Constructor of Node class


  def addKey key
    for k in @keys
      if k == nil or k.class == Node
        next
      elsif key < k
        i =@keys.index(k)
        @keys.insert(i, nil)
        @keys.insert(i,key)
        return i
      end
    end
    @keys.push(key)
    @keys.push(nil)
    return @keys.index(key)
  end  # end of addKey

  def delKey key
    for k in @keys
      if k == nil or k.class == Node
              next
      elsif key == k
        i = @keys.index(k)
        @keys.delete_at(i)
        @keys.delete_at(i)
        return true
      end
    end
    return false
  end

  def size # return NUmber of Keys
    return @keys.size()/2
  end  # end of size

end   #end of Node class

require 'Node'

class B_Tree
  attr_accessor :Root
  def initialize m
    @Root = nil
    @M_WAY = m
  end  # end of Constructor of B_Tree class

  def depth node
    keys = node.keys
    ps= []
    for p in keys
      next if p.class == keys[1].class
      ps.push(depth(p)) if p != nil
    end
    return 1 if ps == []
    return 1+ps.max

  end

  def isFull node
    if node.size() >= @M_WAY-1
      return true
    else
      return false
    end
  end  # end of isFull

  def isUnder node
    if node.size() <= @M_WAY/2-1
      return true
    else
      return false
    end # end of isUnder
  end

  def inorder node
    if node == nil
      return
    end
    for k in node.keys
      if k.class ==Node
        inorder(k)
      elsif k == nil
        next
      else
        print k,"(",depth(node),") "
      end
    end
  end  # end of inorder

  def left_merge neighbor, parent, node
    keys, n_keys, p_keys = node.keys, neighbor.keys, parent.keys
    n_index = p_keys.index(neighbor)
    neighbor.addKey(p_keys[n_index+1])
    n_keys.pop
    neighbor.keys = n_keys + keys
    2.times {p_keys.delete_at(n_index+1)}
    for k in neighbor.keys
      if k.class == Node
        k.parent = neighbor
      end
    end
  end

  def right_merge  neighbor, parent, node
    keys, n_keys, p_keys = node.keys, neighbor.keys, parent.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index+1])
    keys.pop
    node.keys = keys + n_keys
    2.times {p_keys.delete_at(n_index+1)}
    for k in node.keys
      if k.class == Node
        k.parent = node
      end
    end
  end

  def left_loan neighbor, parent, node
    p_keys , n_keys,keys = parent.keys, neighbor.keys,node.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index-1])
    keys[0],keys[2] = keys[2],keys[0]
    p_keys[n_index-1] = n_keys[n_keys.size-2]
    keys[0] = n_keys[n_keys.size-1]
    keys[0].parent = node if keys[0] != nil
    neighbor.keys = n_keys.slice(0,n_keys.size() -2)
  end

  def right_loan neighbor, parent, node
    p_keys , n_keys,keys = parent.keys, neighbor.keys, node.keys
    n_index = p_keys.index(node)
    node.addKey(p_keys[n_index+1])
    p_keys[n_index+1] = n_keys[1]
    keys[keys.size-1] = n_keys[0]
    n_keys[0].parent =node if n_keys[0] != nil
    neighbor.keys = n_keys.slice(2,n_keys.size()-2)
  end

  def search skey
    cur_node = @Root
    found = false
    begin
      s_node = cur_node
      keys = cur_node.keys
      for k in keys
        cur_node = k if k == keys[keys.size-1]
        next if k.class == Node or k == nil
        if skey == k
          found = true
          break
        elsif skey < k
          cur_node = keys[keys.index(k)-1]
          break
        end       # end of if
      end         # end of for

    end while !found and cur_node!=nil
    return found, s_node
  end             # end of search

  def insert nkey
    if @Root == nil
      @Root = Node.new(nil,nkey)
      return true
    else
      # Tree 가 비어있지 않을 때
      duplicate, node = search(nkey)
      if duplicate
        puts "중복되는 데이터를 삽입하였습니다 #{nkey}"
        return false
      end
      newNode = nil
      while true # 잘 들어갈때 까지.
        unless isFull(node)
          # Node에 여유가 있을 때
          i=node.addKey(nkey)
          keys = node.keys()
          keys[i+1] = newNode
          return true
        else
          i=node.addKey(nkey)
          keys = node.keys()
          keys[i+1] = newNode
          if node.size % 2 == 0 : center_index = keys.size/2+1
          else center_index = keys.size/2
          end
          leftkeys = keys.slice(0,center_index)
          rightkeys = keys.slice(center_index+1,keys.size - center_index)
          node.keys = leftkeys
          newNode = Node.new(node.parent,rightkeys)
          tmpkeys = newNode.keys
          for p in tmpkeys
            if p.class == Node
              p.parent = newNode
            end
          end
          if node.parent == nil
            # 부모 노드가 존재하지 않을 때
            @Root = Node.new(nil,keys[center_index])
            rkeys = @Root.keys
            rkeys[0],rkeys[2] = node, newNode
            node.parent = newNode.parent = @Root
            return true
          else
            # 부모 노드가 존재할 경우
            nkey = keys[center_index]
            node = node.parent
          end # end of 부모노드가 존재하지 않을 때
        end   # end of 노드에 여유가 있을 때

      end     # end of while
    end       # end of 트리가 비어있지 않을 때
  end         # end of insert

  def delete dkey
    if @Root == nil
      puts "비어있는 트리입니다. " 
    end
    found, node = search(dkey)
    if not found
      puts "없는 키에대한 삭제입니다 #{dkey}"
      return false
    end
    keys = node.keys
    if keys[0] == nil
      #leaf Node일때
      node.delKey(dkey)
      @Root = nil if @Root.size() <1 
      return true if (not isUnder node) or nil == @Root
      # Under flow 처리 루틴
      parent = node.parent
      # LEAF 노드 삭제 하는거
      until parent == nil

        p_keys = parent.keys
        n_index = p_keys.index(node)
        if n_index != p_keys.size() -1
          #오른쪽 집에서 빌리기
          neighbor = p_keys[n_index+2]
          if neighbor.size()-1 > @M_WAY/2-1
            # 옆집이 부자면
            right_loan(neighbor, parent, node)
            return true
          else
            # 옆집도 거지면
            right_merge(neighbor, parent,node)
            grandson,parent ,node =node, parent.parent,parent
            return true if not isUnder node
          end

        else
          #왼쪽 집에서 빌리기
          neighbor = p_keys[n_index-2]
          # 오른쪽 집 없어서 왼쪽집
          if neighbor.size()-1 > @M_WAY/2-1
            # 왼쪽집 부자면
            left_loan(neighbor, parent, node)
            return true
          else
            # 왼쪽집 거지면
            left_merge(neighbor, parent,node)
            grandson, parent ,node = neighbor, parent.parent,parent
            return true if not isUnder node
          end
        end

      end
      #Root까지 왔을때 처리 하는거
      if @Root.size <1
        @Root = grandson
        grandson.parent = nil
      end
      return true
    else
      # leaf node 가 아닐때
      i=keys.index(dkey)
      p = keys[i+1]
      ch_node = p
      until p == nil
        ch_node = p
        ch_keys = p.keys
        p=ch_keys[0]
      end
      ckeys = ch_node.keys
      c_key = ckeys[1]
      delete(c_key)
      found, node = search(dkey)
      keys = node.keys
      i=keys.index(dkey)
      keys[i] = c_key
      return true
    end
  end

end    # end of B_Tree class

// SolarSystem.cpp : Defines the entry point for the console application.
//

//self rotation 자전
//orbiting 공전

/*
* self rotation표현하기 위해 
* rotation axis : +y  (0,1,0)
* rotation angle : 얼마나 돌았나 
*/

#define _USE_MATH_DEFINES
#include 
#include 

void init();
void display();
void idle();
void draw_axes();
void draw_cube();

float moon_selfrot_angle;
float moon_radius,earth_radius ;
float moon_orbit_angle,earth_selfrot_angle;
float moon_orbit_raidus;
float   sun_radius,earth_orbit_raidus,earth_orbit_angle;

void main(int argc, char* argv[])
{
	glutInit(&argc, argv);
	glutInitDisplayMode(GLUT_DEPTH | GLUT_DOUBLE | GLUT_RGBA);  
	glutInitWindowPosition(100, 100);
	glutInitWindowSize(640, 640);
	glutCreateWindow("GLUT tutorial");
	glutDisplayFunc(display);
	glutIdleFunc(idle);
	init();
	glutMainLoop();
}


void init()
{
	glClearColor(1.0f, 1.0f, 1.0f, 1.0f);
	glEnable(GL_DEPTH_TEST);

	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();  
	gluPerspective(45.0f, 1.0f, 0.001f, 10000.0f);    // don't care at this moment

	sun_radius=10.0f;
	earth_orbit_raidus=26.0f;
	earth_orbit_angle= 0.0f;
	moon_radius=0.7f;
	moon_selfrot_angle = 0.0f;
	moon_orbit_angle=0.0f;
	moon_orbit_raidus=3.5f;
	earth_radius=1.2f;
	earth_selfrot_angle=0.0f;
}


void display()
{
	glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);

	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();  
	gluLookAt(50.0, 50.0, 50.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);

	draw_axes();
	// DRAW the SUn

	glPushMatrix();

	glScalef(sun_radius,sun_radius,sun_radius);
	glColor3f(1.0f,0.0f,0.0f);
	draw_cube();
	glPopMatrix();



	glTranslatef(earth_orbit_raidus*cos(2*M_PI*earth_orbit_angle/360),0.0f,
		earth_orbit_raidus*sin(2*M_PI*earth_orbit_angle/360));


	glPushMatrix(); // 지구랑 달을 묶어서 위의 트렌스레이션을 하기위해
	// 중괄호 같이 묶는다는 느낌.
	//지구
	
	glPushMatrix();	/////////////////////////////////////
	//현재 MV메트릭스를 저장하고 POP때 불러온다 
	// 이게 계층척 그래픽스의 핵심. 모델간의 계층관계를 표현하기 위해.
	// 기존의 I 메트릭스를 PUSH 
	glRotatef(earth_selfrot_angle,0.5,0.5,0);
	glScalef(earth_radius,earth_radius,earth_radius);
	glColor3f(0.0f,1.0f,0.0f);
	draw_cube();
	glPopMatrix();	///////////////////////////////////
	// 기존의 pUSH 했던 I매트릭스를 pOP

	

	//dRAW THE MOON
	// 360 : 2*M_PI = Moon_orbit_angle : x ==> 2*M_PI*moon_orbit_angle/360 
	glTranslatef(moon_orbit_raidus*cos(2*M_PI*moon_orbit_angle/360),0.0f,
		moon_orbit_raidus*sin(2*M_PI*moon_orbit_angle/360));

	glScalef(moon_radius,moon_radius,moon_radius);
	glColor3f(0.5f, 0.5f, 0.5f);
	glRotatef(moon_selfrot_angle,0,-1,0);
	draw_cube();

	glPopMatrix();
	glutSwapBuffers();
}


void draw_axes()
{
	glBegin(GL_LINES);
	// x axis 
	glColor3f(0.2f, 0.2f, 0.2f);
	glVertex3f(-10.0f, 0.0f, 0.0f);
	glColor3f(1.0f, 0.0f, 0.0f);
	glVertex3f( 10.0f, 0.0f, 0.0f);
	// y axis 
	glColor3f(0.2f, 0.2f, 0.2f);
	glVertex3f(0.0f, -10.0f, 0.0f);
	glColor3f(0.0f, 1.0f, 0.0f);
	glVertex3f(0.0f,  10.0f, 0.0f);
	// z axis
	glColor3f(0.2f, 0.2f, 0.2f);
	glVertex3f(0.0f, 0.0f, -10.0f);
	glColor3f(0.0f, 0.0f, 1.0f);
	glVertex3f(0.0f, 0.0f,  10.0f);  
	glEnd();
}

void draw_cube()
{
	glBegin(GL_QUADS);
	// front
	glVertex3f( 0.5f,  0.5f,  0.5f);
	glVertex3f(-0.5f,  0.5f,  0.5f);
	glVertex3f(-0.5f, -0.5f,  0.5f);
	glVertex3f( 0.5f, -0.5f,  0.5f);
	// back
	glVertex3f( 0.5f,  0.5f, -0.5f);
	glVertex3f( 0.5f, -0.5f, -0.5f);
	glVertex3f(-0.5f, -0.5f, -0.5f);
	glVertex3f(-0.5f,  0.5f, -0.5f);
	// top
	glVertex3f( 0.5f,  0.5f,  0.5f);
	glVertex3f( 0.5f,  0.5f, -0.5f);
	glVertex3f(-0.5f,  0.5f, -0.5f);
	glVertex3f(-0.5f,  0.5f,  0.5f);
	// bottom
	glVertex3f( 0.5f, -0.5f,  0.5f);
	glVertex3f(-0.5f, -0.5f,  0.5f);
	glVertex3f(-0.5f, -0.5f, -0.5f);
	glVertex3f( 0.5f, -0.5f, -0.5f);
	// left
	glVertex3f(-0.5f,  0.5f,  0.5f);
	glVertex3f(-0.5f,  0.5f, -0.5f);
	glVertex3f(-0.5f, -0.5f, -0.5f);
	glVertex3f(-0.5f, -0.5f,  0.5f);
	// right
	glVertex3f( 0.5f,  0.5f,  0.5f);
	glVertex3f( 0.5f, -0.5f,  0.5f);
	glVertex3f( 0.5f, -0.5f, -0.5f);
	glVertex3f( 0.5f,  0.5f, -0.5f);
	glEnd();
}


void idle()
{
	// TODO: ...
	earth_orbit_angle+=0.01f;
	if(earth_orbit_angle > 360){
		earth_orbit_angle = 0.0f;
	}

	moon_selfrot_angle+=0.01;//degree (도)

	if(moon_selfrot_angle > 360){
		moon_selfrot_angle = 0.0f;
	}
	moon_orbit_angle+=0.04; //  
	if(moon_orbit_angle > 360){
		moon_orbit_angle= 0.0f;
	}
	earth_selfrot_angle+=0.06f;
	if(earth_selfrot_angle > 360)
		earth_selfrot_angle=0.0f;

	glutPostRedisplay();
}

class Tree:

    def __init__(self):
        self.Root = None
 

class Node:

    def __init__(self,key):
        self.key = key
        self.rightChild = self.leftChild = None
        

# -*- coding : ms949 -*-
import Tree,Node
import sys

class BST:

    def search(self,tree,s_key):
        if (tree == None): return None,None
        parent, curr = None,tree.Root
        while(curr!=None):
            if(curr.key == s_key): break
            parent = curr
            if(curr.key > s_key): curr = curr.leftChild
            else: curr = curr.rightChild
        return parent,curr

    def inorder(self,node):
        if(node==None):
            return
        self.inorder(node.leftChild)
        sys.stdout.write(str(node.key))
        sys.stdout.write("("+str(self.depth(node))+")"+" ")
        self.inorder(node.rightChild)

    def depth(self,node):
        if(node==None): return 0;
        elif(node.rightChild!=None and node.leftChild != None):
            return 1+max(self.depth(node.rightChild),self.depth(node.leftChild))
        elif(node.leftChild==None): return 1+self.depth(node.rightChild)
        elif(node.rightChild==None): return 1+self.depth(node.leftChild)
        else: return 1

    def insert(self,tree,new_key):
        q, p = self.search(tree, new_key)
        if(p != None):
            print("Duplicate key error")
            return False
        newNode = Node.Node(new_key)
        if(tree.Root==None): tree.Root = newNode
        elif (new_key < q.key): q.leftChild=newNode
        else: q.rightChild = newNode
        return True

    def delete(self,tree, d_key):
        q, p = self.search(tree, d_key)
        if(p==None):
            print("There are no key to delete.")
            return False
        if(p.leftChild==None and p.rightChild==None):
            if(q == None):
                tree.Root = None
                return True
            if(q.leftChild == p): q.leftChild = None
            else: q.rightChild = None
        elif(p.leftChild!=None and p.rightChild!=None):
            if(self.depth(p.leftChild) > self.depth(p.rightChild)):
                # Depth of leftSubTree is larger than Right
                exchangeNode = p.leftChild
                while(exchangeNode.rightChild!=None):
                    exchangeNode = exchangeNode.rightChild
            else:
                # Depth of rightSubTree is larger than Left
                exchangeNode = p.rightChild
                while(exchangeNode.leftChild!=None):
                    exchangeNode = exchangeNode.leftChild

            self.delete(tree, exchangeNode.key)
            p.key,exchangeNode.key = exchangeNode.key,p.key


        elif(p.leftChild!=None):
            if(q.leftChild == p): q.leftChild = p.leftChild
            else: q.rightChild = p.leftChild
        else:
            if(q.leftChild == p): q.leftChild = p.rightChild
            else: q.rightChild = p.rightChild
        return True

# -*- coding: ms949 -*-
import BST
import sys

class AVL(BST.BST):
    def __init__(self):
        self.bf_stack=[]
        self.node_stack=[]

    def BFof(self,node):
        return self.depth(node.leftChild)-self.depth(node.rightChild)

    def insert(self,tree,key):
        if super(AVL,self).insert(tree,key) == False: return False
        if self.isAVL(tree,key) :
            del self.bf_stack[:]
            del self.node_stack[:]
        else: self.makeAVL(tree,key)
        return True

    def delete(self,tree,key):
        if super(AVL,self).delete(tree, key)==False: return False
        if self.isAVL(tree,key) :
            del self.bf_stack[:]
            del self.node_stack[:]
        else: self.makeAVL(tree,key)
        return True

    def isAVL(self,tree,key):
        parent,gabage = self.search(tree, key)
        if parent == None: return True
        if len(self.bf_stack)==3:
            self.bf_stack.remove(self.bf_stack[0])
            self.node_stack.remove(self.node_stack[0])
        bf=self.BFof(parent)
        self.bf_stack.append(bf)
        self.node_stack.append(parent)
        if(abs(bf)>1):
            return False
        return self.isAVL(tree,parent.key)

    def makeAVL(self,tree,key):
        if(len(self.bf_stack)==2):
            gabage,C = self.search(tree,key)
            self.node_stack.insert(0,C)
            self.bf_stack.insert(0,self.BFof(C))

        if len(self.bf_stack) == 3:

            if self.bf_stack[1] < 0 and self.bf_stack[2] > 0:
                print("insert",str(key),"=> LR")
                self.RL_LR(tree,self.node_stack[1],self.node_stack[2])

            elif self.bf_stack[1] > 0 and self.bf_stack[2] < 0:
                print("insert",str(key),"=> RL")
                self.RL_LR(tree,self.node_stack[2],self.node_stack[1])

            elif self.bf_stack[1] * self.bf_stack[2] > 0:
                sys.stdout.write("insert "+str(key))
                self.node_stack.remove(self.node_stack[0])
                self.LL_RR(tree)
        del self.bf_stack[:]
        del self.node_stack[:]


    def LL_RR(self,tree):
        A,B=self.node_stack[1],self.node_stack[0]
        parent,gabage = self.search(tree,A.key)
        if parent == None: tree.Root =B
        elif parent.leftChild == A: parent.leftChild = B
        else: parent.rightChild = B

        if self.bf_stack[1] > 0 and self.bf_stack[2] > 0:
            A.leftChild,B.rightChild = B.rightChild, A
            print(" => LL")
        elif self.bf_stack[1] < 0 and self.bf_stack[2] < 0:
            A.rightChild,B.leftChild = B.leftChild, A
            print(" => RR")

    def RL_LR(self,tree,left,right):
        parent,gabage = self.search(tree,self.node_stack[2].key)
        C = self.node_stack[0]
        if parent == None: tree.Root = C
        elif parent.leftChild == self.node_stack[2]: parent.leftChild = C
        else: parent.rightChild =C
        C.leftChild,C.rightChild,left.rightChild,right.leftChild 
              = left,right ,C.leftChild,C.rightChild