树结构是算法与数据结构中都非常重要的一部分,各种高效的搜索与排序算法都有树的影子.常用的树结构有binary tree(二叉树)与balanced search tree(平衡搜索树).平衡搜索树又包含2-3 tree, red-black tree(RBT,红黑树)和B-Tree(B树).由于极大的压缩了生成树的高度,可以进行高效检索运算.
Binary Tree
二叉树,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。堆排序算法就是基于二叉堆(Binary heap)来实现的.二叉树也是平衡二叉树的基础.
树和二叉树的三个主要差别：
树的结点个数至少为1，而二叉树的结点个数可以为0；
树中结点的最大度数没有限制，而二叉树结点的最大度数为2；
树的结点无左、右之分，而二叉树的结点有左、右之分。
完全二叉树和满二叉树
满二叉树：一棵深度为k，且有2^k-1个节点成为满二叉树
完全二叉树：深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中序号为1至n的节点对应时，称之为完全二叉树.
Complete Binary Tree Full Binary Tree
总节点k 2^{h-1}<k<2^h-1 k = 2^h-1
树高h h = log_2k+1 h = log_2(k+1)
二叉树遍历: 前序遍历,中序遍历及后续遍历.
前序遍历: 左子树,根,右子树
中序遍历: 根,左子树,右子树
后续遍历: 左子树,右子树,根
深度优先遍历及广度优先遍历
深度优先遍历: 通过堆栈实现
广度优先遍历: 通过队列实现
Binary Search Tree (BST)
二叉搜索树(有时也称二叉排序树)是二叉树的一种,二叉搜索树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
其实插入,检索,删除都较简单.在最差情况下效率为O(n),下面的几种平衡搜索树是都是基于BST的优化版本.
Balanced Search Trees (平衡搜索树)
2-3 Tree (2-3-4 Tree)
2-3树的节点分为2种:含有2个儿子的叫2节点,含有3个儿子节点的叫3节点.2-3-4树就是也有4节点的平衡树.2-3-4树比2-3树稍微复杂一些,因为节点种类更多,因此下面都以2-3树为例.
2-3树是一种完美平衡树,从根节点到空节点的每条路径都有相同的长度.
插入与检索保证是c*lgN的时间内完成.
树的高度:
最坏: lgN (全是2节点)
最好: log_3(N)≈0.631*lgN(全是3节点)
对于百万个节点高度大约12~20,十亿个节点高度大概18~30.也就意味着在百万条数据中检索需要20步左右,十亿条数据中需要大约30步,可见其对于检索来说是非常高效的.
这里有一个pdf文件很清楚的讲解了2-3树的插入,节点分裂及删除过程.
虽然直接实现2-3树理论上可行,但是由于需要维护多种节点类型,在检索时需要多次比较,插入时如有临时4节点生成,需要回溯到根节点来分裂节点,涉及大量的分裂操作,因此一般并不直接使用2-3树,而是用更加聪明的实现:这就是下面的2种平衡搜索树.
Red-Black Tree (RBT)
红黑树（Red-Black Tree）是二叉搜索树（Binary Search Tree）的一种改进,是2-3树的一种表现。我们知道二叉搜索树在最坏的情况下可能会变成一个链表（当所有节点按从小到大的顺序依次插入后）。而红黑树在每一次插入或删除节点之后都会花O（log N）的时间来对树的结构作修改，以保持树的平衡。也就是说，红黑树的查找方法与二叉搜索树完全一样；插入和删除节点的的方法前半部分节与二叉搜索树完全一样，而后半部分添加了一些修改树的结构的操作。
红黑树的每个节点上的属性除了有一个key、3个指针：parent、lchild、rchild以外，还多了一个属性：color。它只能是两种颜色：红或黑。而红黑树除了具有二叉搜索树的所有性质之外，还具有以下4点性质：
1. 根节点是黑色的。
2. 空节点是黑色的（红黑树中，根节点的parent以及所有叶节点lchild、rchild都不指向NULL，而是指向一个定义好的空节点）。
3. 红色节点的父、左子、右子节点都是黑色(没有节点有2条红色链接)。
4. 在任何一棵子树中，每一条从根节点向下走到空节点的路径上包含的黑色节点数量都相同。
有了这几条规则，就可以保证整棵树的平衡，也就等于保证了搜索的时间为O（log N）。
但是在插入、删除节点后，就有可能破坏了红黑树的性质。所以我们要做一些操作来把整棵树修补好。
红黑树其实就是2-3树的实现,总有一个2-3树与红黑树完全对等,看下图:
红黑树操作: 左旋,右旋,颜色反转
左旋:如果节点指向右孩子节点的链接为红色,需要旋转到左边,旋转方法见下图:
左旋前
左旋后
右旋:如节点指向父节点和指向左孩子节点的链接同时为红色,需要使用右旋来临时提升该节点.
右旋前
右旋后
颜色反转:如果节点指向左右孩子节点的链接同时为红色,需要将节点颜色反转(改变节点指向父节点的链接为红色,同时设置指向左右孩子几点的链接为黑色)
反转前
翻转后
红黑树插入:二叉树搜索直到null节点,插入红色节点,调整树结构.
单节点红黑树插入:
2-节点(不是2个节点)插入:做标准BST插入,新节点为红色,如果新节点在右边,左旋
2个节点红黑树插入的三种情况:
3-节点插入:做标准BST插入,新节点为红色,使用左旋,右旋,颜色反转这些手段来维持红黑树的要求.
3-节点插入可能比较复杂,因为可能需要不断调整树的结构.下面是2个例子:
红黑树删除:做标准二叉树删除,然后调整树结构.(picture from here)
删除最大元素:由于是删除最大元素,因此一直访问右子树
删除最小元素:一直访问左子树
删除任意位置元素
红黑树的作者之一sedgewick的PDF
由于red-black tree的复杂性，sedgewick在08年重新审视了红黑树的实现,提出了left-leaning red-black tree,大大简化了red-black tree的实现难度，代码非常简洁清晰。
Left-leaning红黑树是红黑树的一种,其内部使用left-leaning(左斜)链接像胶水一样来将3节点变为2节点.也等价定义为:
1.平衡搜索树
2.没有节点含有2条红色链接
3.从根节点到空节点的路径包含相同的数目的黑色链接
4.红色链接始终向左.
B-Tree
B树是，存储排序数据并允许以O(log n)的运行时间进行查找，顺序读取，插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。
No comments :
Post a Comment