About
RSS

Bit Focus


万能巧械 - 二叉检索树 [壹]

Posted at Jan 24 2012 - 05:42:01

二叉检索树的查询与检索操作看这里

    从二叉检索树中删除一个元素分多个步骤:
    找到节点与查询操作非常类似, 只不过, 正如插入元素过程中需要将路径上所有节点负载加上 1, 删除过程中, 也需要将节点路径上所有节点负载都减去 1.
    下面是这一部分的实现
void remove_by(key_type const& key)
{
    remove_by_from(key, &root);
}

void remove_at(int position)
{
    remove_at_from(position, &root);
}

static void remove_by_from(key_type const& key, node** parent)
{
    --((*parent)->load);
    if (key < (*parent)->t.key()) {
        remove_by_from(key, &((*parent)->left));
        return;
    }
    if ((*parent)->t.key() < key) {
        remove_by_from(key, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove_at_from(int position, node** parent)
{
    --((*parent)->load);
    int left_load = (NULL == (*parent)->left) ? 0 : (*parent)->left->load;
    if (position < left_load) {
        remove_at_from(position, &((*parent)->left));
        return;
    }
    if (left_load < position) {
        position = position - left_load - 1;
        remove_at_from(position, &((*parent)->right));
        return;
    }
    remove(parent);
}

static void remove(node** n);
    这些函数都是 class binary_search_tree 旗下的. 与插入操作类似地, 这里需要的同样是节点的二级指针, 因为当节点从树中被移除时, 必然伴随着对其父节点对应的子树指针修改.

    找到了节点之后将会有下面 3 种情况
    前两种情况好办, 找到为空的一侧子树, 将另一侧子树接到父节点上, 然后删除当前节点即可. 也就是说当前已经处在容易删除的位置, 可以跳过一个中间步骤. (P 表示待删除节点的父节点)

  +---+
  | P |         +---+
  +---+         | P |
    |           +---+
    V             |
  +---+ ------>   V
  | X |          ---
  +---+           =
 /     \
---   ---
 =     =

     +---+
     | P |         +---+
     +---+         | P |
       |           +---+
       V             |
     +---+           |
     | X | ------>   V
     +---+           .
    /     \         / \
   / \   ---       / L \
  / L \   =       '-----'
 '-----'

    实现代码如下
static void remove(node** n)
{
    if (NULL == (*n)->right) {
        node* rm = *n;
        (*n) = (*n)->left;
        delete rm;
        return;
    }
    if (NULL == (*n)->left) {
        node* rm = *n;
        (*n) = (*n)->right;
        delete rm;
        return;
    }
    rm_after_find_slot(n);
}

static void rm_after_find_slot(node** n);
    上面两个函数亦是 class binary_search_tree 的成员.

    找个合适的位置也并不是什么难事. 比如, 可以找节点左子树的最右侧节点, 让这个替死鬼跟当前节点进行元素交换. 此时, 树的键序会被破坏, 但仅限于即将被删除的元素. 并且, 删除将会被转换为有一侧 (必然是右侧) 子树为空的情况.

        +---+                 +---+                 +---+
        | X |                 | S |                 | S |
        +---+                 +---+                 +---+
       /     \               /     \               /     \
      /       \             /       \             /       \
     / \     / \           / \     / \           / \     / \
    / L \   / R \         / L \   / R \         / L \   / R \
   '-----' '-----' ----> '-----' '-----' ----> '-----' '-----'
    /   \                 /   \                 /   \
   /     .               /     .               /     .
  / \     .             / \     .             / \     .
 /   \     .           /   \     .           /   \     .
'-----'     .         '-----'     .         '-----'     .
           +---+                 +---+                  /\
           | S |                 | X |                 /  \
           +---+                 +---+                / SL \
          /     \               /     \              '------'
         /\    ---             /\    ---
        /  \    =             /  \    =
       / SL \                / SL \
      '------'              '------'

    同时, 为了维护节点负载数据的正确性, 在从左子树根节点向下寻找的过程中, 需要给每个节点的负载减 1
static void rm_after_find_slot(node** n)
{
    node** most_right_in_left = &((*n)->left);
    while (NULL != (*most_right_in_left)->right) {
        --((*most_right_in_left)->load);
        most_right_in_left = &((*most_right_in_left)->right);
    }
    std::swap((*n)->t, (*most_right_in_left)->t);
    remove(most_right_in_left); // recursively call remove
}
    综上, 二叉检索树的基本操作实现完毕 (呃, 没有析构函数确实会有内存泄漏的). 不过这些实现仅仅为了说明原理, 其中维护负载计数的部分是异常不安全的.

    理想情况下, 具有 N 个节点的二叉检索树的高度是 log2N, 因此在树中查询元素和随机访问, 添加节点, 删除节点的平均时间开销都将是对数, 与向堆中添加任意元素, 删除极值元素相同, 略大于堆维护极值元素 (常数时间), 但功能简直多得爆表了. 计算机不变魔法, 多功能和高性能必然伴随代价, 代价首先体现在空间开销, 由于堆的底层用个数组就好了, 因此存多少元素就用多少空间, 而二叉树节点则肩负各种关系指针和负载计数, 有额外空间消耗. 此外, 堆还得益于数组的连续存储特性, 在缓存命中啥的将有极大的优势.

    说到缓存, 顺带提一下 B-tree. 将二叉树拓展一下, 设想数据结构 X 叉树, 每个节点中有至多 X - 1 元素, 至多 X 个子树, 并且第 K 个子树中任何元素的值小于节点中第 K 个元素的值, 而第 K 个元素的值小于第 K + 1 个子树中任意元素的值 (如下图, 一棵 4 叉树)

                 +------------+
                 | 3   7   19 |
                 +---+---+----+
       .--------'   /     \    `----------.
+---------+ +---------+  +------------+ +--------+
| 0  1  2 | | 4  5  6 |  | 11  14  16 | | 20  21 |
+---------+ +---------+  +---+--------+ +--------+
                        /    |
               +--------+ +-------+
               | 8 9 10 | | 12 13 |
               +--------+ +-------+

    X 叉树的层数大约是 logXN, N 为树中元素总数, 因此检索一个元素平均开销为 (X - 1)logXN. 这个函数在 X = 2 时 (大于 1 的整数范围内) 取得最小值. 但并不意味着这样一定是最优的. 一个节点包含的元素个数越多, 它的缓存性能将越好, B-tree 就是这样的树, 它被广泛应用于数据库, 文件系统等需要在外部存储设备读写大量数据的情形.

Post tags:   Algorithm  Generic Programming  Order Statistic  B-tree  Data Structure  Template  C++  Binary Search Tree

广告 点击隐藏
希捷 2TB 移动硬盘
雅致睿翼 浑朴大器
为文件找个安全的空间
夏普空气净化器
帝都居家常规设备
我不要做雾霾侠
还我一个干净的房间
入门级 Linux VPS
海外机房免备案 月付 45
512M 内存 / 20G 硬盘
独立 IP / 600G 流量
带指点杆 USB 键盘
将 Thinkpad 的极致体验复刻到任何 PC
从此甩开鼠标, 甩开关节酸痛

Kindle Paperwhite
读万卷书 行万里路
体验舒适的电子阅读

Leave a comment:




Creative Commons License Your comment will be licensed under
CC-NC-ND 3.0


. Back to Bit Focus
NijiPress - Copyright (C) Neuron Teckid @ Bit Focus
About this site