Computer-Science

Search Trees

• 1. Binary Search Trees
• 2. AVL Trees
• 3. Splay Trees
• 4. (2,4) Trees

1. Binary Search Trees

• A binary search tree is a binary tree storing entries (key,value) at its internal nodes and satisfying the following property:
  • Let u, v, and w be three nodes such that u is in the left subtree of v and w is in the right subtree of v.
  • We have key(u) <= key(v) <= key(w)
• External nodes do not store items
• An inorder traversal of a binary search trees visits the keys in increasing order

Binary Search

• Binary search can perform operations of the ordered map
  • Similar to the high-low game
  • At each step, the number of candidate items is halved
  • Terminates after O(logn) steps
  • 

Example: find(7)

Search

• To search for a key k, we trace a downward path starting at the root
• The next node visited depends on the comparison of k with the key of the current node
• If we reach a leaf, the key is not found and we return a null position

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())

Example: find(4)

• Call TreeSearch(4, root)

Insertion

참고 : 티스토리 DEV_NUNU - 이진 검색 트리 2

Step 1) Find k
Step 2) Insert k

• Assume k is not already in the tree, and let w be the leaf reached by the search
• We insert k at node w and expand w into an internal node

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

• put(5,"A")

  • 

• Inserting an entry with key 78

  • 

Removal

참고 : 티스토리 DEV_NUNU - 이진 검색 트리 3

• To perform operation erase(k), we search for key k
• Assume key k is in the tree, and let v be the node storing k
• If node v has a leaf child w, we remove v and w from the tree with operation removeAboveExternal(w), which removes w and its parent
  • An example operation of removeAboveExternal(w)
  • 

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)

• Removing an entry with key 32

Removal (cont.)

• We consider the case where the key k to be removed is stored at a node v whose children are both internal
  • we find the internal node w that follows v in an inorder traversal
  • we copy key(w) into node v
  • we remove node w and its left child z (which must be a leaf) by means of operation removeAboveExternal(z)

Example: Removal

• erase(3)

• Removing an entry with key 65

Performance

• The height h is O(n) in the worst case
• Consider an ordered map with n items implemented by means of a binary search tree of height h
  • Functions find, put and erase take O(h) = O(n) time
• Functions size, empty take O(1)

2. AVL Trees

• An AVL tree is a binary search tree that satisfies the following Height-Balance Property:
  • For every internal node v of T, the heights of the children of v can differ by at most 1 (왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1 입니다.)
• The heigh to fan AVL tree storing n keys is O(logn)
• Adel’son-Vel’skii and Landis
• 
  • An example of an AVL tree where the heights are shown next to the nodes

Insertion

• Insertion is as in a binary search tree
• Always done by expanding an external node.
• Example:
  • 

Trinode Restructuring

• Let (a,b,c) be an inorder listing of x,y,z
• Perform the rotations needed to make b the topmost node of the three
• 

3. Splay Trees

4. (2,4) Trees

• Visualization : 2-3-4 tree (초기 로딩느림 주의)

• A (2,4) tree (also called 2-4 tree or 2-3-4 tree) is a multi-way search with the following properties
  • Node-Size Property
    • every internal node has at most four children
  • Depth Property
    • all the external nodes have the same depth
• Depending on the number of children, an internal node of a (2,4) tree is called a 2-node, 3-node or 4-node

This site is open source. Improve this page.