《数据结构与算法分析》学习笔记-第四章-树

目录

4.1 预备知识

  • 对于大量的输入数据,链表的线程访问时间太慢,不宜使用。二叉查找树大部分操作的运行时间平均为O(logN)
  • 树可以用几种方式定义,定义树的一种自然的方式是递归的方法。一棵树是一些节点的集合。这个集合可以是空集。若非空,则一棵树由称作根节点r以及0个或多个费控的子树T1, T2, …, Tk组成。这些子树中的每一棵的根都被来自根r的一条有向边所连接
  • 每一棵子树的根叫做根r的儿子,而r是每一棵子树的父亲。
  • 一棵树是==N个节点和N-1条边的集合,其中的一个节点叫做根。存在N-1条边的结论是由:每条边都将某个节点连接到它的父亲,而除去根节点的每一个节点都有一个父亲。
  • 每个节点可以有任意多个儿子(可以是0个)。没有儿子的节点叫做树叶(leaf)。具有相同父亲的节点叫做兄弟(sibling)。用类似的方法可以定义祖父和孙子的关系
  • 对任意节点ni,ni的深度(depth)为从根到ni的唯一路径的长。因此,根的深度是0。ni的高(height)是从ni到一片树叶的最长路径的长。因此所有树叶的高是0。一棵树的高等于它的根的高。一棵树的深度等于它最深树叶的深度,等于这棵树的高。
  • 如果存在从n1到n2的一条路径,那么n1是n2的一位祖先,而n2是n1的一个后裔。如果n1!=n2,那么n1是n2的一个真祖先,而n2是n1的一个真后裔

4.1.1 树的实现

typedef struct TreeNode *PtrToNode;
struct TreeNode
{
    ElementType Element;
    PtrToNode FirstChild;
    PtrToNode NextSibling;
}

4.1.2 树的遍历和应用

  1. 先序遍历: 对节点的处理工作是在它的所有儿子节点被处理之前进行的
static void
ListDir(DirectoryOrFile D, int Depth)
{
    if (D is a legitimate entry)
    {
        PrintName(D, Depth);
        if (D is a directory)
        {
            for each child, C, of D
                ListDir(C, Depth+1);
        }
    }
}

void
ListDirectory(DirectoryOrFile D)
{
    ListDir(D, 0);
}
  1. 后序遍历:对节点的处理工作是在它的所有儿子节点被处理之后进行的
static void
SizeDirectory (DirectoryOrFile D)
{
    int TotalSize;
    TotalSize = 0;
    if (D is a legitimate entry)
    {
        TotalSize = FileSize(D);
        if (D is a directory)
            for each child, C, of D
                TotalSize += SizeDirectory(C)
    }
    return TotalSize;
}

4.2 二叉树

  • 二叉树是一棵树,其中每个节点都不能有多余两个的儿子
  • 二叉树的一个性质是平均二叉树的深度要比N小得多,平均深度为O(N的平方根)
  • 二叉查找树深度的平均值为O(logN),但是极端情况下这个深度是可以大到N-1的

4.2.1 实现

具有N个节点的每一棵二叉树,都将需要N+1个NULL指针

typedef struct TreeNode *PtrToNode;
typedef PtrToNode Tree;
struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
}

4.2.2 表达式树

表达式树的树叶是操作数,比如常量或变量,而其它节点为操作符。

  1. 中序遍历inorder traversal(得到中缀表达式):递归的打印出左子树,中间,右子树
  2. 后序遍历postorder traversal(得到后缀表达式):递归的打印出左子树,右子树,中间
  3. 先序遍历preorder traversal(得到前缀表达式):递归的打印出中间,左子树,右子树

构造一棵表达式树

void suffixExpression(char *inputStr)
{
	int cnt, cnt2;
	Stack s = CreateStack();	
	
	for (cnt = 0; inputStr[cnt] != '\0'; cnt++) {
		if ((inputStr[cnt] >= '0') && (inputStr[cnt] <= '9')) {
			PtrToTreeHead numTree = CreateTreeNode();
			numTree->Element = inputStr[cnt];
			printf("Push %c\n", numTree->Element);
			Push(numTree, s);
		}

		for (cnt2 = 0; cnt2 < OPERATOR_TYPE; cnt2++) {
			if (inputStr[cnt] == Operator[cnt2]) {
				PtrToTreeHead operatorTree = CreateTreeNode();
				operatorTree->Element = inputStr[cnt];
				PtrToTreeHead num2Tree = Top(s);
				Pop(s);
				PtrToTreeHead num1Tree = Top(s);;
				Pop(s);
				
				operatorTree->LeftChild = num1Tree;
				operatorTree->RightChild = num2Tree;
				Push(operatorTree, s);
				printf("operator=%c, num1=%c, num2=%c\n", operatorTree->Element, num1Tree->Element, num2Tree->Element);
			}
		}
	}
	
	PtrToTreeHead printTree = Top(s);
	PrintTree(printTree);
	DrstroyTree(printTree);
	DistroyStack(s);
}

4.3 查找树ADT-二叉查找树

  • 使二叉树成为二叉查找树的性质是:对于树中的每个节点X,它的左子树中的所有关键字值都小于X的关键字值,而它的右子树中所有关键字值大于X的关键字值。这意味着该树所有的元素可以用某种统一的方式排序。
  • 由于树的递归定义,通常是递归的编写这些操作的例程。因为二叉查找树的平均深度是O(logN),所以一般不必担心栈空间被耗尽。
  • 二叉查找树节点定义
struct TreeNode;
typedef struct TreeNode *Position;
typedef Position SearchTree;
struct TreeNode {
    ElementType Element;
    Search Left;
    Srarch Right
}
  • MakeEmpty
SearchTree
MakeEmpty(SearchTree treeHead)
{
    if (treeHead == NULL) {
        return NULL;
    }
    if (treeHead->Left != NULL) {
        MakeEmpty(treeHead->Left);
    }
    if (treeHead->Right != NULL) {
        MakeEmpty(treeHead->Right);
    }
    if (treeHead != NULL) {
        free(treeHead);
    }
}
  • Find: 注意测试的顺序。首先判断是否为空树,其次最不可能的情况应该安排在最后进行。这里使用尾递归,可以用一次赋值和一个goto语句代替。尾递归在这里的使用是合理的,因为算法表达式的简明性是以速度的降低为代价的。而这里使用的栈空间的量也只不过是O(logN)而已。
SearchTree
Find(SearchTree treeHead, ElementType Element)
{
    if (treeHead == NULL) {
        return NULL;
    }
    if (Element < treeHead->Element) {
        return Find(treeHead->Left, Element);
    } else if (Element > treeHead->Element) {
        return Find(treeHead->Right, Element);
    } else {
        return treeHead;
    }
}
  • FindMin递归实现
SearchTree
FindMin(SearchTree treeHead)
{
    if (treeHead == NULL) {
        return NULL;
    }
    if (treeHead->Left != NULL) {
        return FindMin(treeHead->Left);
    } else {
        return treeHead;
    }
}
  • FindMin非递归实现
SearchTree
FindMin(SearchTree treeHead)
{
    if (treeHead == NULL) {
        return NULL;
    }
    
    SearchTree tmp = treeHead;
    while (tmp->Left != NULL) {
        tmp = tmp->Left;
    }
    return tmp;
}
  • FindMax递归实现
SearchTree
FindMax(SearchTree treeHead)
{
    if (treeHead == NULL) {
        return NULL;
    }
    if (treeHead->Right != NULL) {
        return FindMin(treeHead->Right);
    } else {
        return treeHead;
    }
}
  • FindMax非递归实现
SearchTree
FindMax(SearchTree treeHead)
{
    if (treeHead == NULL) {
        return NULL;
    }
    
    SearchTree tmp = treeHead;
    while (tmp->Right != NULL) {
        tmp = tmp->Right;
    }
    return tmp;
}
  • Insert: 重复元素不重复插入,保存在某个辅助数据结构中即可,例如表
SearchTree
Insert(SearchTree treeHead, ElementType element)
{
    if (treeHead == NULL) {
        treeHead = (SearchTree)malloc(sizeof(struct TreeNode));
        if (treeHead == NULL) {
            return NULL;
        }
        memset(treeHead, 0, sizeof(struct TreeNode));
        treeHead->Element = element;
        treeHead->Left = treeHead->Right = NULL;
    } else if (element < treeHead->Element) {
        treeHead->Left = Insert(treeHead->Left, element);    
    } else if (element > treeHead->Element) {
        treeHead->Right = Insert(treeHead->Right, element);
    }
    
    return treeHead;
}
  • Delete: 如果节点是一片树叶,那么他可以立即被删除。如果节点有一个儿子,则该节点可以在其父节点调整指针绕过该节点指向它的儿子的时候(原父节点的孙子节点)该节点可以被删除。所删除的节点不再引用,只有在指向它的指针已被省去的情况下才能够被去掉。
SearchTree
Delete(SearchTree T, ElementType element)
{
    SearchTree tmp;
    
    if (T == NULL) {
        printf("Couldn't find element\n");
        return NULL;
    } else if (element < T->element) {
        T->Left = Delete(T->Left, element);
    } else if (element > T->element) {
        T->Right = Delete(T->Right, element);
    } else if (T->Left && T->Right) {
        tmp = T;
        T->Element = tmp->Element;
        T->Right = Delete(T->Right, element); 
    } else {
        tmp = T;
        if (T->Left) {
            T = T->Left;
        } else if (T->Right) {
            T = T->Right;
        }
        free(tmp);
    }
}
  • 懒惰删除:如果删除的次数不多,则通常使用的策略是懒惰删除。即当一个元素要被删除时,它仍留在树中,而是只做了个被删除的记号。这种做法特别是在有重复关键字时很流行,因为此时记录出现频率数的域可以减一。如果树中的实际节点数和“被删除”的节点数相同,那么树的深度预计只上升一个小的常数。因此,存在一个与懒惰删除相关的非常小的时间损耗。再有,如果被删除的关键字是重新插入的,那么分配一个新单元的开销就避免了。

4.3.6 平均情形分析

  • 除MakeEmpty外,我们期望上一节所有的操作都花费O(logN)时间,所有的操作都是O(d),其中d是包含所访问的关键字的结点的深度。本节证明,假设所有的树出现的机会均等。则树的所有结点的平均深度为O(logN)。
  • 一棵树的所有节点的深度的和为内部路径长。
  • 令D(N)是具有N个节点的某棵树T的内部路径长。D(1) = 0。一棵N节点树是由一棵i节点左子树,和一棵(N-i-1)节点右子树,以及深度为零的一个根节点组成。其中0<=i<N。D(i)为根的左子树的内部路径长。但是在原树中,所有这些节点都要加深一度。同理右子树。因此得到:D(N)=D(i)+D(N-i-1)+N-1。如果所有子树的大小都等可能的出现,这对于二叉查找树是成立的,但是对于二叉树则不成立。那么D(i)和D(N-i-1)的平均值都是(1/N)D(j)(j=0 -> j=N-1)的和。于是D(N) = 2/N * (D(j) (j=0 -> j=N-1))+ N – 1。> D(N) = O(NlogN)。因此任意节点的期望深度为O(logN)
  • 我们并不清楚是否所有的二叉查找树都是等可能出现的,上面描述的删除算法有助于使得左子树比右子树深,因为我们总是用右子树的一个节点来代替删除的节点,这种策略的准确效果仍然是未知的。
  • 在没有删除或者使用使用懒惰删除的i情况下,可以证明所有的二叉查找树都是等可能出现的。上述操作的平均运行时间都是O(logN)
  • 树的平衡:任何节点的深度均不得过深。许多算法实现了平衡树,更加复杂,更新平均时间更长,但是防止了处理起来很麻烦的一些简单清醒。例如AVL树
  • 比较新的方法是放弃平衡条件,允许树有任意的深度,但是每次操作之后要使用一个调整规则进行调整。使得后面的操作效率更高。这种类型的数据结构一般属于自调整类结构。在二叉查找树的情况下,对于任意单个运算,我们不再保证O(logN)的时间界。但是可以证明任意连续M次操作在最坏的情形下,花费时间为O(MlogN)。因此这足以防止令人棘手的最坏情形。

4.4 AVL树

  • 一棵AVL树是其每个节点的左子树和右子树的高度最多差一的二叉查找树(空树的高度定为-1)。每一个节点在其节点结构中保留高度信息。
  • 一个AVL树的高度最多为1.44log(N+2) – 1.328,实际上的高度只比logN稍微多一些
  • 在高度为h的AVL树中,最少节点数S(h) = S(h-1) + S(h-2) + 1。对于h=0, S(h) = 1; h=1, S(h)=2。且函数S(h)与斐波那契数列相关。
  • 除去可能的插入外(假设懒惰删除),所有树操作都可以以时间O(logN)执行。
  • 当进行插入操作时,需要更新通向根节点路径上那些节点的所有平衡信息,而插入操作的困难在于,插入一个节点可能破坏AVL树的特性。如果发生这种情况,那么就要把性质恢复以后才认为这一步插入完成。事实上,可以通过对树进行简单的修正来做到,也就是旋转

4.4.1 单旋转

  • 树的其余部分必须知晓旋转节点的变化。顺着新插入的节点,向根部回溯,检查路径上的某个节点A是否不符合AVL性质(左右子树高度差大于1).如果不符合,则该节点的向深处的下一个节点B进行旋转。并且如果B是右子树,则B的左子树成为A的右子树;如果B是左子树,则B的右子树成为A的左子树。
  • 抽象的形容是:把树形象的看成是柔软灵活的,抓住节点B,使劲摇动它,B成为新的跟,A成为B的子树

4.4.2 双旋转

相当于两次单旋转。

4.4.3 实现

  1. 节点定义
struct AvlNode {
    ElementType Element;
    AvlTree Left;
    AvlTree Right;
    int Height;
}
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
  1. Height
static int
Height(Position P)
{
    if (P == NULL) {
        return -1;
    } else {
        return P->Height;
    }
}
  1. Insert
AvlTree
Insert(AvlTree T, ElementType X)
{
    if (T == NULL) {
        T = (struct AvlNode)malloc(sizeof(struct AvlNode));
        if (T == NULL) {
            return NULL;
        }
        memset(T, 0, sizeof(struct AvlNode));
        T->Element = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } else if (X < T->Element) {
        T->Left = Insert(T->Left, X);
        if (Height(T->Left) - Height(T->Right) == 2) {
            if (X < T->Left->Element) {
                T = SingleRotateWithLeft(T);
            } else {
                T = DoubleRotateWithLeft(T);
            }
        }
    } else if (X > T->Element) {
        T->Right = Insert(T->Right, X);
        if (Height(T->Right) - Height(T->Left) == 2) {
            if (X > T->Right->Element) {
                T = SingleRotateRight(T);
            } else {
                T = DoubleRotateRight(T);
            }
        }
    }
    
    T->Height = MAX(Height(T->Left), Height(T->Right)) + 1;
    return T;
}
  1. SingleRotateWithLeft
AvlTree
SingleRotateWithLeft(Position P)
{
    Position P1 = NULL;
    P1 = P->Left;
    P->Left = P1->Right;
    P1->Right = P;
    P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
    P1->Height = Max(Height(P1->Left), Height(P1->Right)) + 1;
    return P1;
}
  1. SingleRotateWithRight
AvlTree
SingleRotateWithRight(Position P)
{
    Position P1 = NULL;
    P1 = P->Right;
    P->Right = P1->Left;
    P1->Left = P;
    P->Height = Max(Height(P->Left) + Height(P->Right)) + 1;
    P1->Height = Max(Height(P1->Left) + Height(P1->Right)) + 1;
    return P1;
}
  1. DoubleRotateWithLeft
AvlTree
DoubleRotateWithLeft(Position P)
{
    P->Left = SingleRotateWithRight(P->Left);
    return SingleRotateWithLeft(P);
}
  1. DoubleRotateWithRight
AvlTree
DoubleRotateWithRight(Position P)
{
    P->Right = SingleRotateWithLeft(P->Right);
    return SingleRotateWithRight(P);
}

4.5 伸展树

  • 当一个节点被访问后,它就要经过一系列AVL树的旋转被放到根上。注意,如果一个节点很深,那么其路径上就存在许多的节点也相对较深,通过重新构造可以使对这些节点的进一步访问所花费的时间变少。因此,如果节点过深,我们还要求重新构造应具有平衡这棵树(到某种程度)的作用。实际使用中,当一个节点被访问时,它就很可能不久再被访问到。且较为频繁。
  • 不要求保留高度或平衡信息,因此节省空间并简化代码

4.6 树的遍历

  • 三种遍历方式
  • 首先处理NULL的情形,然后才是其余工作
  • 程序越紧凑,一些愚蠢的错误出现的可能就越小
  • 层序遍历不是用递归实现的,而是用队列实现的,不使用递归所默示的栈。所有深度为D的节点要在深度为D+1的节点之前进行处理

4.7 B-树

  • 阶:一个节点子节点(子树)数目的最大值
  • 树的根其儿子数在2和M之间
  • 除根外,所有非树叶节点的儿子数在[M/2]到M之间
  • 所有树叶都在相同的深度上
  • 所有的数据都存储在树叶上,每一个内部节点皆含有指向该节点各儿子的指针P1,P2,…,PM和分别代表在子树P2, P3, …, PM中发现的最小关键字的值K1, K2, …, KM-1。有些指针是NULL,而其对应的Ki是未定义的。对于==每一个节点,其子树P1中的所有关键字都小于子树P2的关键字
  • 树叶包含实际数据,这些数据是关键字或者是指向含有这些关键字的记录的指针
  • B树深度最多是log(M/2)N。插入和删除可能需要O(M)的工作量来调整该节点上的所有信息。对于每个插入和删除,最坏情形的运行时间为O(Mlog(M)N) = O((M/logM) logN).查找一次只花费O(logN)时间
  • M最好(合法的)选择是M=3或M=4,当M再增大时插入和删除的时间就会增加
  • 如果使用M阶B树,那么磁盘访问的次数是O(log(M)N),每次磁盘访问花费O(logM)来确定分支的方向,该操作比一般都存储器的区块所花的时间少得多,因此认为是无足轻重的。
  • 当一棵B树得到它的第(M+1)项时,例程不是总去分裂节点,而是搜索能够接纳新儿子的兄弟,此时能够更好的利用空间

参考文献

  1. Mark Allen Weiss.数据结构与算法分析[M].America, 2007

本文作者: CrazyCatJack

本文链接: https://www.cnblogs.com/CrazyCatJack/p/13339994.html

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

关注博主:如果您觉得该文章对您有帮助,可以点击文章右下角推荐一下,您的支持将成为我最大的动力!

人已赞赏
经验教程

翻译:《实用的Python编程》01_07_Functions

2021-2-19 12:35:00

经验教程

《分析与思考 - 降杠杆与风险化解》笔记

2021-2-19 13:18:00

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索