首页 > 代码库 > 二叉查找树 Binary Serach Tree

二叉查找树 Binary Serach Tree

二叉查找树(Binary Serach Tree, BST)是一棵二叉树,树上每个节点存储着一个元素。对于树上每个节点X,它的左子树中所有元素均小于X,而它的右子树中所有元素均大于X。且树上不允许出现相同的节点。

这意味着只要对树做一遍中序遍历,就得到一个有序的序列。

技术分享

   

屏幕剪辑的捕获时间: 2017/5/29 11:09

   

一、基本操作和实现

首先定义结点的结构。

为了避免访问NULL指针,定义一个nil节点作为哨兵节点。

constexpr int l = 0, r = 1;

constexpr int inf = 0x7fffffff;

struct node;

node *nil = 0, *root;

struct node

{

    node *ch[2]; //ch[l]左孩子, ch[r]右孩子

    int val, size, cnt; //, 子树包含元素个数(包括重复), 结点代表元素的个数

    node(int value) : val(value), size(1), cnt(1) { ch[l] = ch[r] = nil; }

    void pull_up() { size = cnt + ch[l]->size + ch[r]->size; } //修正结点的size信息

    int cmp(int v) { return (v < val) ? l : r; } //向左儿子走或是向右儿子走

};

void init()

{

    if (!nil) nil = new node(0);

    nil->ch[l] = nil->ch[r] = nil;

    nil->val = nil->size = nil->cnt = 0;

    root = nil;

}

为了方便说明,下面不区分节点和节点存储的元素。

   

查找操作

用关键字和根节点比较。当根节点存在时:

若小于根节点,则递归到左子树查找;

若大于根节点,则递归到右子树查找;

直到节点等于关键字。

若遍历到一个不存在节点的位置,则查找失败。

bool exist(int val, node *t = root)

{

    if (t == nil) return false;

    else if (val == t->val) return true;

    else return exist(val, t->ch[t->cmp(val)]);

}

   

寻找最值

和查找操作类似。不过总是递归到左(或右)子树查找。当该节点不存在左(或右)儿子时,该节点就是要找的最值。

int min(node *t = root)

{

    if(t->ch[l] != nil) return max(t->ch[l]);

    else return t->val;

}

int max(node *t = root)

{

    if(t->ch[r] != nil) return max(t->ch[r]);

    else return t->val;

}

 

插入操作

和查找操作类似。

当遍历到一个不存在节点的位置时,在该节点的位置新建一个节点。

当该节点已经等于关键字时,意味着出现了重复,根据具体情况选择计数、套个另外的数据结构或者直接不处理。

注意修正size信息。

void insert(int val, node *&t = root) //传引用很重要

{

    if (t == nil) t = new node(val); //找到目标位置

    else if (val == t->val) t->cnt++; //重复

    else insert(val, t->ch[t->cmp(val)]); //递归寻找目标

    t->pull_up();

}

 

删除操作

基本上还是类似于查找操作。

找到相应结点时,先处理计数,若计数已经小于1,才需要删除。

若该节点为叶子,可以直接删除;

若只有一个儿子,可以用它的儿子代替该节点然后删除;

若有两个儿子,则用右子树中的最小节点的值代替该节点的,这个最小节点必定没有左儿子(如果有左儿子,它的左儿子必定比它小,不符合最小节点的设定),然后通过上面两种情况删除这个最小节点。

注意修正size信息。

void remove(int val, node *&t = root)

{

    if (t == nil) return; //找不到目标结点

    else if (val != t->val) remove(val, t->ch[t->cmp(val)]); //递归寻找结点

    else if (--(t->cnt) < 1) //找到结点计数减一检查是否需要删除结点

    {

        if (t->ch[l] == nil || t->ch[r] == nil) //没有儿子或一个儿子

        {

            node *k = (t->ch[l] != nil) ? t->ch[l] : t->ch[r];

            delete t;

            t = k;

        }

        else

        {

            node *k = t->ch[r];

            while (k->ch[l] != nil) k = k->ch[l];

            t->val = k->val; t->cnt = k->cnt;

            k->cnt = 1;

            remove(k->val, t->ch[r]);

        }

    }

    t->pull_up();

}

 

查找K大元素

和查找操作类似。不过是用K左子树的秩+1比较。因为根节点就是中序遍历时的第"左子树的秩+1"个结点,也就是第"左子树的秩+1"大的结点。

K < 左子树的秩+1,递归进入左子树查找;

若左子树的秩+1 <= K <= 左子树的秩+计数,第K大元素就是该节点;

否则递归进入右子树查找第K-(左子树的秩+计数)大结点。

注意处理K<1k>该子树的秩的情况。

int kth(int k, node *t = root)

{

    if (k < 1 || k > t->size) return inf;

    else if (k <= t->ch[l]->size) return kth(k, t->ch[l]); //在左子树

    else if (k <= t->ch[l]->size + t->cnt) return t->val; //就是t

    else return kth(k - t->ch[l]->size - t->cnt, t->ch[r]); //在右子树

}

 

统计小于X的元素个数

和查找操作类似,边查找边统计。

若该节点小于X,则给统计加上左子树的秩+计数,然后递归进入右子树;

若该节点等于X,则给统计加上左子树的秩,直接返回;

若该节点大于X,则递归进入左子树。

遍历至空节点,直接返回0

int get_lower(int val, node *t = root)

{

    if (t == nil) return 0;

    else if (val < t->val) return get_rank(val, t->ch[l]);

    else if (val == t->val) return t->ch[l]->size;

    else return t->ch[l]->size + t->cnt + get_rank(val, t->ch[r]);

}

 

查询X的排名

小于X的元素个数+1

   

二、平衡二叉查找树

naiveBST最大的问题便是经过数次插入和删除操作后,树将会变得不平衡,甚至退化为一条链。

   

技术分享

   

屏幕剪辑的捕获时间: 2017/5/29 11:34

   

为了解决这个问题,平衡二叉查找树(平衡树)应运而生。

   

旋转操作

   

技术分享

   

屏幕剪辑的捕获时间: 2017/5/29 11:48

   

旋转前,k2为父节点,k1k2的子结点。旋转后,k1为父节点,k2k1的子结点。旋转成功让k1上升了一层,k2下降了一层。

观察树,可以得到,旋转不破坏二叉查找树的性质。于是让k1的右儿子Y作为k2的左儿子,再让k2作为k1的右儿子,最后访问k2的父亲,让k1代替k2成为它的儿子。

几乎所有的平衡树都通过旋转操作调整树的形态使树保持平衡。

void rotate(node *&t, int d)

{

    node *k = t->ch[d ^ 1]; //找儿子

    t->ch[d ^ 1] = k->ch[d]; //换儿子

    k->ch[d] = t; //认儿子

    t->pull_up(); k->pull_up();

    t = k; //父亲

}

 

常见的平衡树

现有的平衡树主要有两类:

一类要求每次插入、删除后,检查整棵树是否符合特定的平衡条件,如TreapAVL树、红黑树、Size Balanced Tree。若不符合则通过旋转使得树重新平衡。

另一类平衡树并不强制要求树符合平衡条件,而是每次操作后都使用一次自调整操作改善平衡树,使得后面的操作效率更高。即Splay树。

   

树堆Treap

每次新建节点时给节点一个随机的优先级。从优先级的角度看时,要求树符合堆的性质,即每个节点的优先级都小于(或者都大于)两个儿子的优先级。每次插入和删除后,自底向上检查,将优先度较小的旋转到下方。

代码量小,效率高。功能简单。

   

伸展树Splay

每次访问树之后通过一系列的旋转(称为伸展)将最后一个访问的节点推上根节点的位置。

代码量较小,效率较高,支持快速合并和分裂。稍微改造可以用来维护数列(来自BST高于BST)。

   

非旋转树堆Treap

基于合并和分裂的Treap

代码量较小,效率低,支持快速合并和分裂,同样可以用来维护数列。

   

替罪羊树Scapegoat Tree

每次插入节点后自底向上检查是否符合特定的平衡条件,以最上方的不符合条件的节点作为根,将整棵子树拆散,并重新组装成一棵平衡的二叉树。

代码量一般,平均意义下跑得飞快。

   

Size Balanced Tree

国内OI选手陈启峰发明,要求树的每个节点的一个儿子的秩(即以该节点为根节点的子树的节点数)分别大于或等于另一个儿子的两个儿子的秩。即对于节点X,满足(

代码量一般,效率高。

   

AVL

要求树的每个节点的左右儿子的深度差不超过1。插入和删除后自底向上通过单旋转或双旋转调整。

代码量小,由于树趋于平衡,查找效率高,插入删除效率低。

   

红黑树

为2-3-4树的一种二叉树的实现。将2-3-4树的元素按照一定规则进行着色,按照在2-3-4树插入删除元素对应的方式维护红黑树。

代码量很大,插入效率高于AVL树,查找效率低于AVL树,综合性能最优。

二叉查找树 Binary Serach Tree