首页 > 代码库 > 二叉查找树

二叉查找树

2024-09-10 21:24:47   217人阅读

普通二叉查找树

二叉查找树是指具有下列性质的非空二叉树

  1. 若根结点的左子树不空，则左子树的所有结点值均小于根结点值；
  2. 若根结点的右子树不空，则右子树的所有结点值均不小于根结点值；
  3. 根结的左右树也分别为二叉排序树；

显然，对二叉排序树进行中序遍历，可得出结点值递增的排序序列。

下图即是一棵二叉查找树。

技术分享

其中序遍历为8，11，23，39，46，68，71，75。

树的基本操作

const int MAXN = 101;
struct node {
    int data;       //关键字
    int lch,rch;    //左、右子指针
};
node bst[MAXN];     //二叉查找树
int n;
void init()         //读入数据
{
    int i,t,r=0;
    cin>>n;
    for (i=1;i<=n;i++){
        cin>>t;
        insert(r,t);//将t插入r为根的树中。
    }
}
/*****************插入操作*****************/
void insert(int &root,int t)
{
    if(root==0){
        bst[cnt++].data=http://www.mamicode.com/t;"hljs-keyword">return;
    }
    if(t<bst[root].data)
        insert(bst[root].lch,t);
    else if(t>bst[root].data)
        insert(bst[root].rch,t);
}
/*****************查找操作*****************/
//找到该节点，则返回该节点下标;否则返回-1.
int find(int root,int x)
{
    if(x==bst[root].data)return root;
    if(root==0)return -1;
    if(x>bst[root].data)
        return find(bst[root].rch,x);
    else
        return find(bst[root].lch,x);
}
/*****************删除操作*****************/
/*
删除操作：如果找到该节点，则将该节点删除；如果没有找到，则不做任何事情。
删除操作有些复杂，我们先来分析一下：
如果删除的节点是叶子节点，则直接删除即可。
如果删除的节点只有左儿子或只有右儿子，直接删除，并将该节点的父亲和儿子连接起来，类似于链表的删除。
如果删除的节点有左右儿子，如何处理？
设该节点为x。在x的左子树里边找到最大的节点t,
执行：bst[x].data=http://www.mamicode.com/bst[t].data;>
void delete(int &root,int vx)
{
    if(root==0)return;
    if(bst[root].data>vx)
        delete(bst[root].lc,vx);
    else if(bst[root].data<vx)
        delete(bst[root].rc,vx);
    else {
        if(bst[root].lch==0||bst[root].rch==0)
        root=bst[root].lch+bst[root].rch;
        else{
            int t=bst[root].lch;
            int f=root;
            while(t.rch) { 
                f=t;
                t=bst[t].rch;
            }
            bst[root].data=http://www.mamicode.com/bst[t].data;"hljs-keyword">if(f==root)bst[f].lch=bst[t].lch;  
            else bst[f].rch=bst[t].lch;
        }
    }
}

惰性删除

其实删除操作完全可以粗略地处理。即只将要删除的节点打上标记，并不真正删除。这样的话，简便很多。而在效率上影响不大：如果删除节点很少，完全不会有影响；删除节点即使很多，也不会增加时间复杂度，只是常数上增加而已。
可以看出，在理想情况下，二叉查找数的insert，find，delete等操作的时间复杂度都是O(logN)。但是，如果树退化称为一条链，则insert,find,delete等操作的时间复杂度就是O(N)了。
为了使得在最差情况下，二叉查找数的各项操作也能达到O(logN)的时间复杂度，我们可以将树做一些改进，于是，就有了下面要讲的AVL.

AVL树

平衡二叉树的定义

  • 平衡树（Balanced Tree）：高度为O(logn)的树。

  • 平衡二叉树（Balanced Binary Tree）：由阿德尔森一维尔斯和兰迪斯（Adelson-Velskii and Landis）于1962年首先提出的，所以又称为AVL树。
    空二叉树是AVL树；

    1. TL和TR 是AVL树；
    2. |hL-hR|≤1，hL和hR分别是左子树和右子树的高度

技术分享

AVL树必须具备的特征

  • n个元素的AVL树的高度是O(logn)；
  • 一棵n元素的AVL搜索树能在O(高度)=O(logn+1) 的时间内完成搜索；
  • 将一个新元素插入到一棵n元素的AVL搜索树中，可得到一棵n+1元素的AVL树，这种插入过程可以在O(logn+1)时间内完成；
  • 从一棵n元素的AVL搜索树中删除一个元素，可得到一棵n-1元素的AVL树，这种删除过程可以在O(logn+1)时间内完成。

AVL树的高度

假设Nh是一棵高度为h的AVL树中最小的节点数
Nh=Nh?1+Nh?2+1,N0=0,N1=1<script type="math/tex" id="MathJax-Element-1">N_h=N_{h-1}+N_{h-2}+1,N_0=0,N_1=1</script>

可以看到Nh的定义与斐波那契数列的定义非常相似
Fn=Fn?1+Fn?2+1,F0=0,F1=1<script type="math/tex" id="MathJax-Element-2">F_n=F_{n-1}+F_{n-2}+1,F_0=0,F_1=1</script>

技术分享

AVL树的平衡因子

为每个节点增加一个平衡因子bf。节点x 的平衡因子bf (x)定义为：bf (x)= hL-hR 。
即：x的左子树的高度-x 的右子树的高度。
从AVL树的定义可以知道，平衡因子的可能取值为-1、0、1。
技术分享
如果树中任意一个结点的平衡因子的绝对值大于 1，则这棵二叉树就失去平衡。

AVL树的搜索

如果一棵AVL树有n个节点，其高度可以保持在O(logn)，因此平均搜索长度也可以保持在O(logn)。
二叉搜索树的算法完全适用于AVL树。

AVL树的插入

若一棵二叉搜索树是平衡二叉树，插入某个节点后，可能会变成非平衡二叉树，而且只可能是该节点到根的路径上的节点不平衡了。我们可以通过修正来使它恢复平衡，这中操作就是”旋转“。
如下图所示
技术分享

我们插入了一个节点后，从该节点向上搜索，找到第一个不平衡的节点，对它进行调整即可。可以预见，调整了该节点过后，所有节点都将达到平衡状态。
让我们把必须重新平衡的节点叫做α。当不平衡时，左右子树的高度差为2.
这种不平衡可能出现在下面四种情况中：

  1. 对α的左儿子的左子树进行了一次插入
  2. 对α的左儿子的右子树进行了一次插入
  3. 对α的右儿子的左子树进行了一次插入
  4. 对α的右儿子的右子树进行了一次插入

情形1和4是关于α点的镜像对称，而2和3是关于α点的镜像对称。因此，理论上只有两种情况。

第一种情况是发生在“外边”的情况，即左-左的情况或右-右的情况，该情况可以通过对树的一次单旋转而完成调整。第二种情况是插入发生在“内部”的情况，即（左-右的情况或右-左的情况），该情况通过稍微复杂些的双旋转来处理。

平衡化旋转

平衡化旋转有两类：

  • 单旋转（zig—右旋或zag—左旋）
  • 双旋转（zagzig或zigzag旋转）

如果这三个节点处于一条直线上，则采用单旋转进行平衡化。
如果这三个节点处于一条折线上，则采用双旋转进行平衡化。

技术分享

zig右旋

若在 C 的左子树的左子树上插入结点，使 C 的平衡因子从 1 增加至 2， 需要进行一次顺时针旋转。(以 B 为旋转轴）
技术分享

zag左旋

若在 A 的右子树的右子树上插入结点，使 A 的平衡因子从 -1 改变为 -2，需要进行一次逆时针旋转。(以 B 为旋转轴）
技术分享

zagzig 双旋转

若在 C 的左子树的右子树上插入结点，使 C 的平衡因子从 1 增加至 2， 需要先进行逆时针旋转， 再顺时针旋转。 (以插入的结点 B 为旋转轴）
技术分享

zagzig 双旋转

若在 A 的右子树的左子树上插入结点，使 A 的平衡因子从 -1 改变为 -2，需要先进行顺时针旋转，再逆时针旋转。(以插入的结点 B 为旋转轴）
技术分享

调整必须保证二叉排序树的特性不变

旋转算法

技术分享
zig：新插入节点在不平衡节点的左子树的左子树中；
zag：新插入节点在不平衡节点的右子树的右子树中；
zigzag：新插入节点在不平衡节点的左子树的右子树中；
zagzig：新插入节点在不平衡节点的右子树的左子树中。

zig旋转

技术分享
在左子树D上插入新节点使其高度增1，导致节点A的平衡因子增到 2，造成了不平衡。
为使树恢复平衡，从A沿插入路径连续取3个节点A、B和D，它们处于一条方向为“/”的直线上，需要做LL旋转。
以节点B为旋转轴，将节点A顺时针旋转成为B的右孩子，B代替原来A的位置，原来B的右孩子E转为A的左孩子。

zig旋转的算法
int zig(int r)//右旋
{
    int t=tree[r].lc;
    tree[r].lc=tree[t].rc;
    tree[t].rc=r;
    tree[r].h=max(tree[tree[r].rc].h,tree[tree[r].lc].h)+1;
    tree[t].h=max(tree[tree[t].rc].h,tree[tree[t].lc].h)+1;
    return t;
}

注：假设r一定存在左儿子，右旋过后，t成为根节点。

zag旋转

技术分享
在右子树E中插入一个新节点，该子树高度增1导致节点A的平衡因子变成-2，出现不平衡。
沿插入路径检查三个节点A、C和E。它们处于一条方向为“\”的直线上，需要做zag旋转。
以节点C为旋转轴，让节点A反时针旋转成为C的左孩子，C代替原来A的位置，原来C的左孩子D转为A的右孩子。

左单旋转的算法
int zag(int r) //左旋
{
    int t=tree[r].rc;
    tree[r].rc=tree[t].lc;
    tree[t].lc=r;
    tree[r].h=max(tree[tree[r].rc].h,tree[tree[r].lc].h)+1;
    tree[t].h=max(tree[tree[t].rc].h,tree[tree[t].lc].h)+1;
    return t;
}

备注：r必存在右儿子。

zagzig旋转

技术分享
在子树F或G中插入新节点，该子树的高度增1。节点A的平衡因子变为 2，发生了不平衡。
从节点A起沿插入路径选取3个节点A、B和E，它们位于一条形如“<”的折线上，因此需要进行先左后右的双旋转。
首先以节点E为旋转轴，将节点B**逆时针旋转**，以E代替原来B的位置，做zag旋转。
再以节点E为旋转轴，将节点A**顺时针旋转**，做zig旋转，使之平衡化。

技术分享

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

    二叉查找树


联系
我们