Computer-Science

Searching

Contents


Trees

Terminology Explain Example
Root node without parent A
Child if node u is the parent of node v, v is a child of u A
Internal node node with at least one child A, B, C, F
External node (=Leaf) node without children E, I, J, K, G, H, D
Ancestors of a node parent, grandparent, great-grandparent, etc. ย 
Siblings of a node Any node which shares a parent ย 
Depth of a node number of ancestors (๋…ธ๋“œ์˜ ์†์„ฑ) K์˜ ๊ฒฝ์šฐ, A, B, F์ด๋ฏ€๋กœ 3
Height of a tree maximum depth of any node (ํŠธ๋ฆฌ์˜ ์†์„ฑ) 3
Descendant of a node child, grandchild, great-grandchild, etc. ย 
Subtree tree consisting of a node and its descendants (๋ถ€๋ถ„์ง‘ํ•ฉ ๊ฐ™์€ ๊ฐœ๋…) ย 
Degree number of children of a node (ํŠธ๋ฆฌ์˜ ์†์„ฑ) F์˜ ๊ฒฝ์šฐ, I, J, K์ด๋ฏ€๋กœ 3
Edge a pair of node (u, v) such that u is a parent of v((C, H)) ย 
Path A sequence of nodes such that any two consecutive nodes form an edge A, B, F, J
Ordered tree a tree with a linear ordering defined for the children of each node ย 

1) Preorder Traversal (P-L-R)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-12 - แ…ฉแ„’แ…ฎ 8 55 54

Algorithm preOrder(T,p)
  visit(p)
  for each child q of p
    preOrder(T,q)

2) Postorder Traversal (L-P-R)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-12 - แ…ฉแ„’แ…ฎ 8 57 09

Algorithm postOrder(T,p)
  for each child q of p
    postOrder(T,q)
  visit(p)

3) In-order Traversal

Algorithm inOrder(T,p)
  if ยฌp.isExternal()
    inOrder(T,p.left())
  visit(p)

  if ยฌp.isExternal()
    inOrder(T,p.right())

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-12 - แ…ฉแ„’แ…ฎ 8 51 32

4) Euler Tour Traversal

Algorithm eulerTour(T,p)
  visit(p) on the left // preOrder
  if ยฌp.isExternal()
    eulerTour(T,p.left())
  visit(p) from below // inOrder
  if ยฌp.isExternal()
    eulerTour(T,p.right())
  visit(p) on the right // postOrder

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-13 - แ…ฉแ„Œแ…ฅแ†ซ 11 32 22

์ด์ง„ ํŠธ๋ฆฌ (Binary Tree)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-12 - แ…ฉแ„’แ…ฎ 4 55 28

Properties of Binary Trees

Arithmetic Expression Tree

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-12 - แ…ฉแ„’แ…ฎ 4 55 55

์ด์ง„ ํƒ์ƒ‰ ํŠธ๋ฆฌ (Binary Serarch Tree)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 5 04 25

Algorithm TreeSearch(k, u)
  if u.isExternal()
    return u

  if k < u.key()
    return TreeSearch(k, u.left())
  else if k = u.key()
    return u
  else // k > u.key()
    return TreeSearch(k, u.right())

BST์—์„œ์˜ Insertion

์ฐธ๊ณ  : https://new93helloworld.tistory.com/115?category=691027

public:
    void insertItem(const Key& k, const Element& e) // insert (key, element)
        { inserter(k, e); }
protected:
    BTPosition inserter(const Key& k, const Element& e) { // insert utillity
        BTPosition p = finder(k, T.root()); // find insertion spot
        // ๋‚ด๋ถ€๋…ธ๋“œ์ธ ๊ฒฝ์šฐ
        while (T.isInternal(p)) // key already exists?
            // look further
            p = finder(k, T.rightChild(p)); // leftChild๋กœ ํ•ด๋„ ์•„๋ฌด ์ƒ๊ด€ ์—†์Œ
        // ์™ธ๋ถ€๋…ธ๋“œ์ธ ๊ฒฝ์šฐ
        T.expandExternal(p); // add new node here
        setItem(p, BSTItem(k, e)); // store (key, element)
        return p;
    }

Example: Insertion

Removal

์ฐธ๊ณ  : https://new93helloworld.tistory.com/116?category=691027

public:
    // remove using key
    void removeElement(const Key& k) throw(NonexistentElementException) {
        BTPosition p = finder(k, T.root()); // find the node
        if (p.isNull()) // not found?
            throw NonexistentElementException("Remove nonexistent element");
        remover(p); // remove it
    }
protected:
    BTPosition remover(const BTPosition& r) { // remove utility
        BTPosition p;
        if (T.isExternal(T.leftChild(r))) // left is external?
            p = T.leftChild(r); // remove from left
        else if (T.isExternal(T.rightChild(r))) // right is external?
            p = T.rightChild(r); // remove from right
        else {
            p = T.rightChild(r); // p = replacement
            do
                p = T.leftChild(p); // ... right subtree
            while (T.isInternal(p));
            setItem(r, T.parent(p).element()); // copy parent(p) to r
        }
        return T.removeAboveExternal(p); // remove p and parent
    }

Example: Removal

erase(4)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 5 57 47

Removing an entry with key 32

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 5 58 38

Removal (cont.)

Example: Removal

erase(3)

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 6 15 50

Removing an entry with key 65

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 6 17 30

Performance

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2021-12-14 - แ…ฉแ„’แ…ฎ 6 50 59

๊ท ํ˜• ํŠธ๋ฆฌ (Balanced Tree)

2-4 Tree

แ„‰แ…ณแ„แ…ณแ„…แ…ตแ†ซแ„‰แ…ฃแ†บ 2022-04-18 - แ…ฉแ„Œแ…ฅแ†ซ 1 37 22

Red-Black Tree

A red-black tree is a representation of a (2,4) tree by means of a binary tree whose nodes are colored red or black

Hashing

ํŠน์ง•

ํ•ด์‹ฑ๊ณผ ์ด์ง„ ํŠธ๋ฆฌ

์—ฐ์‡„๋ฒ• (chaining)

์„ ํ˜• ํƒ์‚ฌ๋ฒ• (linear probing)

์ด์ค‘ ํ•ด์‹ฑ (double hashing)

Grid File (๋‹ค์ฐจ์› Hashing)

๊ธฐ์ˆ˜ ํƒ์ƒ‰ (Radix searching)

๋””์ง€ํ„ธ ํƒ์ƒ‰ ํŠธ๋ฆฌ (Digital Search Tree)

๊ธฐ์ˆ˜ ํƒ์ƒ‰ ํŠธ๋ผ์ด (Radix Search Trie)

ํŒจํŠธ๋ฆฌ์ƒค ํŠธ๋ฆฌ (Patricia)

์™ธ๋ถ€ ํƒ์ƒ‰ (external seraching)

B-tree

B+-tree

B+-tree์˜ ์„ฑ๋Šฅ (B-tree์™€์˜ ๋น„๊ต)

R-tree