简单学习数据结构
数据结构简介
数据结构是为实现对计算机数据有效使用的各种数据组织形式,服务于各类计算机操作。不同的数据结构具有各自对应的适用场景,旨在降低各种算法计算的时间与空间复杂度,达到最佳的任务执行效率。
常见的数据结构可分为[线性数据结构]和[非线性数据结构],线性数据结构:[数组]、[链表]、[栈]、[队列];非线性数据结构:[树]、[图]、[散列表]、[堆]。
数组
数组是将相同类型的元素存储与连续内存空间的数据结构,其长度不可变。
1// 初始化一个长度为5的数组arr
2int[] arr = new int[5];
3// 元素赋值
4arr[0] = 1;
5arr[1] = 2;
6arr[2] = 3;
7arr[3] = 4;
8arr[4] = 5;
或者可以使用直接赋值的初始化方法
1int[] arr = {1,2,3,4,5};
可变数组
[可变数组]是经常使用的数据结构,其基于数组和扩容机制实现,相比普通数组更加灵活。常用操作有:访问元素、添加元素、删除元素。
1// 初始化可变数组
2List<Integer> arr = new ArrayList<>();
3// 向尾部添加元素
4arr.add(1);
5arr.add(2);
6arr.add(3);
7arr.add(4);
8arr.add(5);
链表
[链表]是以节点为单位,每个元素都是一个独立对象,在内存空间的存储是非连续的。链表的节点对象具有两个成员变量:[值 val]、[后继节点引用 next]。
1class ListNode {
2 int val; // 节点值
3 ListNode next; // 后继节点引用
4 ListNode (int x) { val = x; }
5}
建立链表需要实例化每个节点,并构建各节点的引用指向。
1// 实例化节点
2ListNode n1 = new ListNode(4); //节点head
3ListNode n2 = new ListNode(5);
4ListNode n3 = new ListNode(1);
5
6//构建引用指向
7n1.next = n2;
8n2.next = n3;
栈
[栈]是一种具有[先入后出]特点的抽象数据结构,可使用数组或链表实现。
1Stack<Integer> stack = new Stack<>();
通过常用操作 [入栈 push()] , [出栈 pop()] ,展示了栈的先入后出特性。
1stack.push(1); // 元素 1 入栈
2stack.push(2); // 元素 2 入栈
3stack.pop(); // 出栈 -> 元素 2
4stack.pop(); // 出栈 -> 元素 1
注意:通常情况下,不推荐使用 Java 的 Vector 以及其子类 Stack,而一般将 LinkedList 作为栈来使用。
1LinkedList<Integer> stack = new LinkedList<>();
2
3stack.addLast(1); // 元素 1 入栈
4stack.addLast(2); // 元素 2 入栈
5stack.removeLast(); // 出栈 -> 元素 2
6stack.removeLast(); // 出栈 -> 元素 1
队列
队列是一种具有 [先入先出] 特点的抽象数据结构,可使用链表实现。
1Queue<Integer> queue = new LinkedList<>();
通过常用操作 [入队 push()] ,[出队 pop()] ,展示了队列的先入先出特性。
1queue.offer(1); // 元素 1 入队
2queue.offer(2); // 元素 2 入队
3queue.poll(); // 出队 -> 元素 1
4queue.poll(); // 出队 -> 元素 2
树
树是一种非线性数据结构,根据子节点数量可分为 [二叉树] 和 [多叉树] ,最顶层的节点称为 [根节点 root] 。以二叉树为例,每个节点包含三个成员变量:[值 val]、 [左子节点 left] 、[右子节点 right] 。
二叉树
二叉树的每个结点至多只有两颗子树(不存在大于 2 的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第 i 层至多有 2 i-1个结点。深度为 K 的二叉树至多有 2 k-1个结点;对任何一颗二叉树 T,如果其终端结点树为 n0,度为 2 的的结点数为 n 2 ,则 n 0 =n 2 +1。
示例:
满二叉树和完全二叉树
满二叉树:除最后一层无任何结点外,每一层上的所有结点都有两个子结点。也可以这样理解,除叶子结点之外的所有节点均有两个子结点。结点数达到最大值,所有叶子结点必须在同一层上。
性质:
- 一棵树深度为 h,最大层数为 k,深度与最大层数相同,k=h;
- 叶子树为 2h;
- 第 k 层的结点数是:2k-1;
- 总结点数是:2k-1,且总结点数一定是奇数。
完全二叉树:若设二叉树的深度为 h,除第 h 层外,其他各层(1~(h-1)层)的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
注:完全二叉树是效率很高的数据结果,堆是一种完全二叉树或者近似完全二叉树,所以效率极高,像十分常用的排序算法、Dijkstra 算法、Prim 算法等都要用堆才能优化,二叉排序树的效率也要借助平衡性来提高,而平衡性基于完全二叉树。
二叉树的性质
- 在非空二叉树中,第 i 层的结点总数不超过 2i-1,i>=1;
- 深度为 n 的二叉树最多有 2h-1 个结点(h>=1),最少有 h 个结点;
- 对于任意一颗二叉树,如果其叶子结点数为 N0,而度数为 2 的结点总数为 N2,则 N0=N2+1;
- 具有 n 个结点的完全二叉树的深度为 log2(n+1);
- 有 N 个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若 I 为结点编号
如果 I>1,则其父结点的编号为 1/2;
如果 2I<=N,则其左儿子(即左子树的根结点)的编号为 2I;若 2I>N,则无左儿子;
如果 2I+1<=N,则其右儿子的结点编号为 2I+1;若 2I+1>N,则无右儿子。 - 给定 N 个结点,能构成 h(N)中不同的二叉树,其中 h(N)为卡特兰树的第 N 项,h(n)=C(2*n,n)/(n+1)。
- 设有 i 个结点,I 为所有支点的道路长度总和,J 为叶的道路长度总和 J=I+2i。
二叉查找树
定义:又称为是二叉排序树(Binary Sort Tree)或二叉搜索树。二叉排序树或者是一颗空树,或者是具有下列性质的二叉树
- 若左子树不空,则左子树所有结点的值均小于它的根结点的值;
- 若右子树不空,则右子树所有结点的值均大于或等于它的根结点的值;
- 左、右子树也分别为二叉排序树;
- 没有键值相等的结点。
性质:对二叉查找树进行中序遍历,即可得到有序的数列。
时间复杂度:它和二分查找一样,插入和查找的时间复杂度均为 o(logn),但是在最坏的情况下仍然会有 O(n)的时间复杂度。原因在于插入和删除元素的时候。树没有保持平衡。我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是平衡查找树设计的初衷。
二叉查找树的高度决定了二叉查找树的查找效率。
插入过程:
- 若当前的二叉查找树为空,则插入的元素为根结点;
- 若插入的元素值小于根结点值,则将元素插入到左子树中;
- 若插入的元素值不小于根结点值,则将元素插入到右子树中。
三种删除的情况处理:
- p 为叶子结点,直接删除该结点,在修改其父结点的指针(注意分是根结点和不是根结点),如图 a;
- p 为单支结点(即只有左子树或右子树)。让 p 的子树与 p 的父亲结点相连,删除 p 即可(注意分是根结点和不是根结点),如图 b;
- p 的左子树和右子树均不空,找到 p 的后继 y,因为 y 一定没有左子树,所以可以删除 y,并让 y 的父亲结点成为 y 的右子树的父亲结点,并用 y 的值代替 p 的值;或者方法二是找到 p 的前驱 x,x 一定没有右子树,所以可以直接删除 x,并让 x 的父亲结点成为 y 的左子树的父亲结点,如果 c。
二叉树实现相关源码
插入操作
1struct node
2{
3 int val;
4 pnode lchild;
5 pnode rchild;
6};
7
8pnode BT = NULL;
9
10
11//递归方法插入节点
12pnode insert(pnode root, int x)
13{
14 pnode p = (pnode)malloc(LEN);
15 p->val = x;
16 p->lchild = NULL;
17 p->rchild = NULL;
18 if(root == NULL){
19 root = p;
20 }
21 else if(x < root->val){
22 root->lchild = insert(root->lchild, x);
23 }
24 else{
25 root->rchild = insert(root->rchild, x);
26 }
27 return root;
28}
29
30//非递归方法插入节点
31void insert_BST(pnode q, int x)
32{
33 pnode p = (pnode)malloc(LEN);
34 p->val = x;
35 p->lchild = NULL;
36 p->rchild = NULL;
37 if(q == NULL){
38 BT = p;
39 return ;
40 }
41 while(q->lchild != p && q->rchild != p){
42 if(x < q->val){
43 if(q->lchild){
44 q = q->lchild;
45 }
46 else{
47 q->lchild = p;
48 }
49 }
50 else{
51 if(q->rchild){
52 q = q->rchild;
53 }
54 else{
55 q->rchild = p;
56 }
57 }
58 }
59 return;
60}
删除操作
1<P>
2<PRE>bool delete_BST(pnode p, int x) //返回一个标志,表示是否找到被删元素
3{
4 bool find = false;
5 pnode q;
6 p = BT;
7 while(p && !find){ //寻找被删元素
8 if(x == p->val){ //找到被删元素
9 find = true;
10 }
11 else if(x < p->val){ //沿左子树找
12 q = p;
13 p = p->lchild;
14 }
15 else{ //沿右子树找
16 q = p;
17 p = p->rchild;
18 }
19 }
20 if(p == NULL){ //没找到
21 cout << "没有找到" << x << endl;
22 }
23
24 if(p->lchild == NULL && p->rchild == NULL){ //p为叶子节点
25 if(p == BT){ //p为根节点
26 BT = NULL;
27 }
28 else if(q->lchild == p){
29 q->lchild = NULL;
30 }
31 else{
32 q->rchild = NULL;
33 }
34 free(p); //释放节点p
35 }
36 else if(p->lchild == NULL || p->rchild == NULL){ //p为单支子树
37 if(p == BT){ //p为根节点
38 if(p->lchild == NULL){
39 BT = p->rchild;
40 }
41 else{
42 BT = p->lchild;
43 }
44 }
45 else{
46 if(q->lchild == p && p->lchild){ //p是q的左子树且p有左子树
47 q->lchild = p->lchild; //将p的左子树链接到q的左指针上
48 }
49 else if(q->lchild == p && p->rchild){
50 q->lchild = p->rchild;
51 }
52 else if(q->rchild == p && p->lchild){
53 q->rchild = p->lchild;
54 }
55 else{
56 q->rchild = p->rchild;
57 }
58 }
59 free(p);
60 }
61 else{ //p的左右子树均不为空
62 pnode t = p;
63 pnode s = p->lchild; //从p的左子节点开始
64 while(s->rchild){ //找到p的前驱,即p左子树中值最大的节点
65 t = s;
66 s = s->rchild;
67 }
68 p->val = s->val; //把节点s的值赋给p
69 if(t == p){
70 p->lchild = s->lchild;
71 }
72 else{
73 t->rchild = s->lchild;
74 }
75 free(s);
76 }
77 return find;
78}
查找操作
1pnode search_BST(pnode p, int x)
2{
3 bool solve = false;
4 while(p && !solve){
5 if(x == p->val){
6 solve = true;
7 }
8 else if(x < p->val){
9 p = p->lchild;
10 }
11 else{
12 p = p->rchild;
13 }
14 }
15 if(p == NULL){
16 cout << "没有找到" << x << endl;
17 }
18 return p;
19}
平衡二叉树
对于一般的二叉搜索树(Binart Search Tree),其期望高度(即为一颗平衡树时)为 log2n,其各操作的时间复杂度 O(log2n)同时也由此决定。但是,在某些极端的情况下(如在插入的序列是有序的时),二叉搜索树将退化成近似链或队列,此时,其操作的时间复杂度将退化成线性的,即 O(n)。我们可以通过随机化建立二叉搜索树来尽量的避免这种情况,但是在进行了多次的操作之后,由于在删除时,我们总是选择将待删除结点的后继代替它本身,这样就回造成总是右边的结点数目减少,以至于树向左偏沉。这同时也会造成树的平衡性收到破坏,提高它的操作的时间复杂度。于是就有了平衡二叉树。
定义:平衡二叉树(Balanced Binary Tree)又被称为 AVL 树(有别于 AVL 算法),且具有以下性质,它是一颗空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一颗平衡二叉树。平衡二叉树的 常用算法有红黑树、AVL 树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好的维持在 O(log2n),大大降低了操作的时间复杂度。
最小二叉平衡树的结点公式:
F(n)=F(n-1)+F(n-2)+1
这个类似于一个递归的数列,可以参考 Fibonacci 数列,i 时根结点,F(n-1)是左子树的结点数量,F(n-2)是右子树的结点数量。
平衡查找树之 AVL 树
定义:AVL 树是最先发明的平衡二叉查找树,在 AVL 中任何结点的两个儿子子树的高度最大差别为 1,所以它被成为高度平衡树,n 个结点的 AVL 树最大深度约 1.44log2n。插入、查找和删除在平均和最坏情况下都是 O(logn)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。这个方案很好的解决了二叉查找树退化成链表的问题。把插入、查找和删除的时间复杂度最好情况和最坏情况都维持在了 O(logN)。但是频繁旋转会使插入和删除牺牲掉 O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。
AVL 树的自平衡操作—旋转
ACL 树最关键也是最难的一步操作就是旋转。旋转主要是为了实现 AVL 树在实施了插入和删除操作以后,树重新回到平衡的方法。下面我们重点研究一下 AVL 树的旋转。
对于一个平衡的结点,由于任意结点最多有两个儿子,因此高度不平衡时,此结点的两棵树的高度差 2,容易看出,这种不平衡出现在下面四种情况。
- 6 结点的左子树 3 结点高度比右子树 7 结点大 2,左子树 3 结点的左子树 1 结点高度大于右子树 4 结点,这种情况成为左左。
- 6 结点的左子树 2 结点高度比右子树 7 结点大 2,左子树 2 结点的左子树 1 结点高度小于右子树 4 结点,这种情况成为左右。
- 2 结点的左子树 1 结点高度比右子树 5 结点小 2,右子树 5 结点的左子树 3 结点高度大于右子树 6 结点,这种情况成为右左。
- 2 结点的左子树 1 结点高度比右子树 4 结点小 2,右子树 4 结点的左子树 3 结点高度小于右子树 6 结点,这种情况成为右右。
从图 2 可以看出,1 和 4 两种情况是对成的,这两种情况的旋转算法也是一致的,只需要经过一次旋转就可以到达目标,我们称之为单旋转。2 和 3 两种情况也是对称的,这两种情况的旋转算法也是一致的,需要进行两种算法,我们称之为双旋转。
单旋转
单旋转是针对于左左和右右这两种情况的解决方法,这两种情况是对称的,只要解决了左左这种情况,右右就很好办了。图 3 是左左情况的解决方案,结点 k2 不满足平衡特性,因为它的左子树 k1 比右子树 Z 深 2 层,而且 k1 子树中,更深的一层的是 k1 的左子树 X 子树,所以属于左左情况。
为使树恢复平衡,我们把 k2 变成这棵树的根结点,因为 k2 大于 k1,把 k2 置于 k1 的右子树上,而原本在 k1 右子树的 Y 大于 k1,小于 k2,就把 Y 置于 k2 的左子树上,这种既满足了二叉查找树的性质,又满足了平衡二叉树的性质。
这样的操作只需要一部分指针改变,结果我们得到另外一颗二叉查找树,它是一颗 AVL 树,因为 X 向上一移动了一层,Y 还停留在原来的层面上,Z 向下移动了一层。整棵树的新高度和之前没有在左子树上插入的高度相同,插入操作使得 X 高度长高了。因此,由于这棵子树高度没有变化,所以通往根结点的路径就不需要在继续旋转了。
双旋转
对于左右和右左这两种情况,单旋转不能使它达到一个平衡状态,要经过两次旋转。双旋转是针对于这两种情况的解决方案,同样的,这样两种情况也是对称的,只要解决了左右这种情况,右左就很好办了。图 4 是左右情况的解决方案,结点 k3 不满足平衡特性,因此它的左子树 k1 比右子树 Z 深 2 层,而且 k1 子树中,更深的一层的是 k1 的右子树 k2 子树,所以属于左右情况。
为使树恢复平衡,我们需要进行两部。第一步,把 k1 作为根,进行一次右右旋转,旋转之后就变成了左左情况,所以第二步在进行一次左左旋转,最后得到了一颗以 k2 为根的平衡二叉树
AVL 树实现源码
1//AVL树节点信息
2template<class T>
3class TreeNode
4{
5 public:
6 TreeNode():lson(NULL),rson(NULL),freq(1),hgt(0){}
7 T data;//值
8 int hgt;//高度
9 unsigned int freq;//频率
10 TreeNode* lson;//指向左儿子的地址
11 TreeNode* rson;//指向右儿子的地址
12};
13//AVL树类的属性和方法声明
14template<class T>
15class AVLTree
16{
17 private:
18 TreeNode<T>* root;//根节点
19 void insertpri(TreeNode<T>* &node,T x);//插入
20 TreeNode<T>* findpri(TreeNode<T>* node,T x);//查找
21 void insubtree(TreeNode<T>* node);//中序遍历
22 void Deletepri(TreeNode<T>* &node,T x);//删除
23 int height(TreeNode<T>* node);//求树的高度
24 void SingRotateLeft(TreeNode<T>* &k2);//左左情况下的旋转
25 void SingRotateRight(TreeNode<T>* &k2);//右右情况下的旋转
26 void DoubleRotateLR(TreeNode<T>* &k3);//左右情况下的旋转
27 void DoubleRotateRL(TreeNode<T>* &k3);//右左情况下的旋转
28 int Max(int cmpa,int cmpb);//求最大值
29
30 public:
31 AVLTree():root(NULL){}
32 void insert(T x);//插入接口
33 TreeNode<T>* find(T x);//查找接口
34 void Delete(T x);//删除接口
35 void traversal();//遍历接口
36
37};
38//计算节点的高度
39template<class T>
40int AVLTree<T>::height(TreeNode<T>* node)
41{
42 if(node!=NULL)
43 return node->hgt;
44 return -1;
45}
46//求最大值
47template<class T>
48int AVLTree<T>::Max(int cmpa,int cmpb)
49{
50 return cmpa>cmpb?cmpa:cmpb;
51}
52//左左情况下的旋转
53template<class T>
54void AVLTree<T>::SingRotateLeft(TreeNode<T>* &k2)
55{
56 TreeNode<T>* k1;
57 k1=k2->lson;
58 k2->lson=k1->rson;
59 k1->rson=k2;
60
61 k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
62 k1->hgt=Max(height(k1->lson),k2->hgt)+1;
63}
64//右右情况下的旋转
65template<class T>
66void AVLTree<T>::SingRotateRight(TreeNode<T>* &k2)
67{
68 TreeNode<T>* k1;
69 k1=k2->rson;
70 k2->rson=k1->lson;
71 k1->lson=k2;
72
73 k2->hgt=Max(height(k2->lson),height(k2->rson))+1;
74 k1->hgt=Max(height(k1->rson),k2->hgt)+1;
75}
76//左右情况的旋转
77template<class T>
78void AVLTree<T>::DoubleRotateLR(TreeNode<T>* &k3)
79{
80 SingRotateRight(k3->lson);
81 SingRotateLeft(k3);
82}
83//右左情况的旋转
84template<class T>
85void AVLTree<T>::DoubleRotateRL(TreeNode<T>* &k3)
86{
87 SingRotateLeft(k3->rson);
88 SingRotateRight(k3);
89}
90//插入
91template<class T>
92void AVLTree<T>::insertpri(TreeNode<T>* &node,T x)
93{
94 if(node==NULL)//如果节点为空,就在此节点处加入x信息
95 {
96 node=new TreeNode<T>();
97 node->data=x;
98 return;
99 }
100 if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中插入x
101 {
102 insertpri(node->lson,x);
103 if(2==height(node->lson)-height(node->rson))
104 if(x<node->lson->data)
105 SingRotateLeft(node);
106 else
107 DoubleRotateLR(node);
108 }
109 else if(node->data<x)//如果x大于节点的值,就继续在节点的右子树中插入x
110 {
111 insertpri(node->rson,x);
112 if(2==height(node->rson)-height(node->lson))//如果高度之差为2的话就失去了平衡,需要旋转
113 if(x>node->rson->data)
114 SingRotateRight(node);
115 else
116 DoubleRotateRL(node);
117 }
118 else ++(node->freq);//如果相等,就把频率加1
119 node->hgt=Max(height(node->lson),height(node->rson));
120}
121//插入接口
122template<class T>
123void AVLTree<T>::insert(T x)
124{
125 insertpri(root,x);
126}
127//查找
128template<class T>
129TreeNode<T>* AVLTree<T>::findpri(TreeNode<T>* node,T x)
130{
131 if(node==NULL)//如果节点为空说明没找到,返回NULL
132 {
133 return NULL;
134 }
135 if(node->data>x)//如果x小于节点的值,就继续在节点的左子树中查找x
136 {
137 return findpri(node->lson,x);
138 }
139 else if(node->data<x)//如果x大于节点的值,就继续在节点的左子树中查找x
140 {
141 return findpri(node->rson,x);
142 }
143 else return node;//如果相等,就找到了此节点
144}
145//查找接口
146template<class T>
147TreeNode<T>* AVLTree<T>::find(T x)
148{
149 return findpri(root,x);
150}
151//删除
152template<class T>
153void AVLTree<T>::Deletepri(TreeNode<T>* &node,T x)
154{
155 if(node==NULL) return ;//没有找到值是x的节点
156 if(x < node->data)
157 {
158 Deletepri(node->lson,x);//如果x小于节点的值,就继续在节点的左子树中删除x
159 if(2==height(node->rson)-height(node->lson))
160 if(node->rson->lson!=NULL&&(height(node->rson->lson)>height(node->rson->rson)) )
161 DoubleRotateRL(node);
162 else
163 SingRotateRight(node);
164 }
165
166 else if(x > node->data)
167 {
168 Deletepri(node->rson,x);//如果x大于节点的值,就继续在节点的右子树中删除x
169 if(2==height(node->lson)-height(node->rson))
170 if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
171 DoubleRotateLR(node);
172 else
173 SingRotateLeft(node);
174 }
175
176 else//如果相等,此节点就是要删除的节点
177 {
178 if(node->lson&&node->rson)//此节点有两个儿子
179 {
180 TreeNode<T>* temp=node->rson;//temp指向节点的右儿子
181 while(temp->lson!=NULL) temp=temp->lson;//找到右子树中值最小的节点
182 //把右子树中最小节点的值赋值给本节点
183 node->data=temp->data;
184 node->freq=temp->freq;
185 Deletepri(node->rson,temp->data);//删除右子树中最小值的节点
186 if(2==height(node->lson)-height(node->rson))
187 {
188 if(node->lson->rson!=NULL&& (height(node->lson->rson)>height(node->lson->lson) ))
189 DoubleRotateLR(node);
190 else
191 SingRotateLeft(node);
192 }
193 }
194 else//此节点有1个或0个儿子
195 {
196 TreeNode<T>* temp=node;
197 if(node->lson==NULL)//有右儿子或者没有儿子
198 node=node->rson;
199 else if(node->rson==NULL)//有左儿子
200 node=node->lson;
201 delete(temp);
202 temp=NULL;
203 }
204 }
205 if(node==NULL) return;
206 node->hgt=Max(height(node->lson),height(node->rson))+1;
207 return;
208}
209//删除接口
210template<class T>
211void AVLTree<T>::Delete(T x)
212{
213 Deletepri(root,x);
214}
215//中序遍历函数
216template<class T>
217void AVLTree<T>::insubtree(TreeNode<T>* node)
218{
219 if(node==NULL) return;
220 insubtree(node->lson);//先遍历左子树
221 cout<<node->data<<" ";//输出根节点
222 insubtree(node->rson);//再遍历右子树
223}
224//中序遍历接口
225template<class T>
226void AVLTree<T>::traversal()
227{
228 insubtree(root);
229}
平衡二叉树之红黑树
定义:红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组,称之为“对称二叉 B 树”。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的:它可以在 O(logn)的时间内做查找,插入和删除,这里的 n 是树中元素的数目。
红黑树和 AVL 树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用中有价值,而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值。
性质:红黑树是每个结点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制的一般要求以外,对于任何有效的红黑树我们增加了如下的恶额外要求
- 结点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色(叶子是 NIL 结点)。
- 每个红色结点必须有两个黑色的子结点。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
- 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的,因为操作比如插入、删除和查找某个值的最快情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。,
红黑树的自平衡操作
因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持 O(logn)次。
我们首先以二叉查找树的方法增加结点并标记它为红色。如果设置为黑色,就会导致根到叶子的路径上有一条路上多一个格外的黑结点,这个是很难调整的(违背性质 5)。但是设为红色结点后,可能会导致出现两个连续红色结点的冲突,那么可以通过颜色调换(color flips)和树旋转来调整。下面要进行什么操作取决于其他临近结点的颜色。同人类的家族树中一样,我们将使用术语叔父结点来指一个结点的父结点的兄弟结点,注意:
- 性质 1 和性质 3 总是保持着
- 性质 4 只在增加红色结点、重绘黑色结点为红色,或做旋转时受到威胁。
- 性质 5 只在增加黑色结点、重绘红色结点为黑色,或做旋转时受到威胁。
插入操作:
假设,将要插入的结点标为 N,N 的父结点标为 P,N 的祖父结点标为 G,N 的叔父结点标为 U,在途中展示的任何颜色要么是由它所处情形这些所作的假定,要么是假定所暗含的。
-
情形 1:该树为空树,直接插入根结点的位置,违反性质 1,把结点颜色由红改为黑即可。
-
情形 2:插入结点 N 的父结点 P 为黑色,不违反任何性质,无需做任何修改。在这种情形下,树仍是有效的。性质 5 也未受到威胁,尽管新结点 N 有两个黑色叶子子结点;但由于新结点 N 是红色,通过它的每个字结点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色结点,所以依然满足这个性质。
注:情形 1 很简单,情形 2 中 P 为黑色,一切安然无事,但 P 为红就不一样了,下边是 P 为红的各种情况,也是真正难懂的地方。 -
情形 3:如果父节点 P 和叔父节点 U 二者都是红色,(此时新插入节点 N 做为 P 的左子节点或右子节点都属于情形 3,这里右图仅显示 N 做为 P 左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点 G 为红色(用来保持性质 4)。现在我们的新节点 N 有了一个黑色的父节点 P。因为通过父节点 P 或叔父节点 U 的任何路径都必定通过祖父节点 G,在这些路径上的黑节点数目没有改变。但是,红色的祖父节点 G 的父节点也有可能是红色的,这就违反了性质 4。为了解决这个问题,我们在祖父节点 G 上递归地进行上述情形的整个过程(把 G 当成是新加入的节点进行各种情形的检查)。比如,G 为根节点,那我们就直接将 G 变为黑色(情形 1);如果 G 不是根节点,而它的父节点为黑色,那符合所有的性质,直接插入即可(情形 2);如果 G 不是根节点,而它的父节点为红色,则递归上述过程(情形 3)。
-
情形 4:父节点 P 是红色而叔父节点 U 是黑色或缺少,新节点 N 是其父节点的左子节点,而父节点 P 又是其父节点 G 的左子节点。在这种情形下,我们进行针对祖父节点 G 的一次右旋转; 在旋转产生的树中,以前的父节点 P 现在是新节点 N 和以前的祖父节点 G 的父节点。我们知道以前的祖父节点 G 是黑色,否则父节点 P 就不可能是红色(如果 P 和 G 都是红色就违反了性质 4,所以 G 必须是黑色)。我们切换以前的父节点 P 和祖父节点 G 的颜色,结果的树满足性质 4。性质 5 也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点 G,现在它们都通过以前的父节点 P。在各自的情形下,这都是三个节点中唯一的黑色节点。
-
情形 5:父节点 P 是红色而叔父节点 U 是黑色或缺少,并且新节点 N 是其父节点 P 的右子节点而父节点 P 又是其父节点的左子节点。在这种情形下,我们进行一次左旋转调换新节点和其父节点的角色; 接着,我们按情形 4 处理以前的父节点 P 以解决仍然失效的性质 4。注意这个改变会导致某些路径通过它们以前不通过的新节点 N(比如图中 1 号叶子节点)或不通过节点 P(比如图中 3 号叶子节点),但由于这两个节点都是红色的,所以性质 5 仍有效。
注:插入实际上是原地算法,因为上述所有调用都是用了尾部递归。
删除操作:
**如果需要删除的结点有两个儿子,那么问题可以被转化成删除另一个只有一个儿子的结点的问题。**对于二叉查找树,在删除带有两个非叶子儿子的节点的时候,我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素,并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点,它必定有少于两个非叶子的儿子。因为只是复制了一个值,不违反任何性质,这就把问题简化为如何删除最多有一个儿子的节点的问题。它不关心这个节点是最初要删除的节点还是我们从中复制出值的那个节点。
我们只需要讨论删除只有一个儿子的节点 (如果它两个儿子都为空,即均为叶子,我们任意将其中一个看作它的儿子)。如果我们删除一个红色节点(此时该节点的儿子将都为叶子节点),它的父亲和儿子一定是黑色的。所以我们可以简单的用它的黑色儿子替换它,并不会破坏性质 3 和性质 4。通过被删除节点的所有路径只是少了一个红色节点,这样可以继续保证性质 5。另一种简单情况是在被删除节点是黑色而它的儿子是红色的时候。如果只是去除这个黑色节点,用它的红色儿子顶替上来的话,会破坏性质 5,但是如果我们重绘它的儿子为黑色,则曾经通过它的所有路径将通过它的黑色儿子,这样可以继续保持性质 5。
需要进一步讨论的是在要删除的节点和它的儿子二者都是黑色的时候 ,这是一种复杂的情况。我们首先把要删除的节点替换为它的儿子。出于方便,称呼这个儿子为 N (在新的位置上),称呼它的兄弟(它父亲的另一个儿子)为 S 。在下面的示意图中,我们还是使用 P 称呼 N 的父亲,SL 称呼 S 的左儿子,SR 称呼 S 的右儿子。
红黑树实现源码
1<PRE>#define BLACK 1
2#define RED 0
3
4using namespace std;
5
6class bst {
7private:
8
9 struct Node {
10 int value;
11 bool color;
12 Node *leftTree, *rightTree, *parent;
13
14 Node() {
15 color = RED;
16 leftTree = NULL;
17 rightTree = NULL;
18 parent = NULL;
19 value = 0;
20 }
21
22 Node* grandparent() {
23 if (parent == NULL) {
24 return NULL;
25 }
26 return parent->parent;
27 }
28
29 Node* uncle() {
30 if (grandparent() == NULL) {
31 return NULL;
32 }
33 if (parent == grandparent()->rightTree)
34 return grandparent()->leftTree;
35 else
36 return grandparent()->rightTree;
37 }
38
39 Node* sibling() {
40 if (parent->leftTree == this)
41 return parent->rightTree;
42 else
43 return parent->leftTree;
44 }
45 };
46
47 void rotate_right(Node *p) {
48 Node *gp = p->grandparent();
49 Node *fa = p->parent;
50 Node *y = p->rightTree;
51
52 fa->leftTree = y;
53
54 if (y != NIL)
55 y->parent = fa;
56 p->rightTree = fa;
57 fa->parent = p;
58
59 if (root == fa)
60 root = p;
61 p->parent = gp;
62
63 if (gp != NULL) {
64 if (gp->leftTree == fa)
65 gp->leftTree = p;
66 else
67 gp->rightTree = p;
68 }
69
70 }
71
72 void rotate_left(Node *p) {
73 if (p->parent == NULL) {
74 root = p;
75 return;
76 }
77 Node *gp = p->grandparent();
78 Node *fa = p->parent;
79 Node *y = p->leftTree;
80
81 fa->rightTree = y;
82
83 if (y != NIL)
84 y->parent = fa;
85 p->leftTree = fa;
86 fa->parent = p;
87
88 if (root == fa)
89 root = p;
90 p->parent = gp;
91
92 if (gp != NULL) {
93 if (gp->leftTree == fa)
94 gp->leftTree = p;
95 else
96 gp->rightTree = p;
97 }
98 }
99
100 void inorder(Node *p) {
101 if (p == NIL)
102 return;
103
104 if (p->leftTree)
105 inorder(p->leftTree);
106
107 cout << p->value << " ";
108
109 if (p->rightTree)
110 inorder(p->rightTree);
111 }
112
113 string outputColor(bool color) {
114 return color ? "BLACK" : "RED";
115 }
116
117 Node* getSmallestChild(Node *p) {
118 if (p->leftTree == NIL)
119 return p;
120 return getSmallestChild(p->leftTree);
121 }
122
123 bool delete_child(Node *p, int data) {
124 if (p->value > data) {
125 if (p->leftTree == NIL) {
126 return false;
127 }
128 return delete_child(p->leftTree, data);
129 } else if (p->value < data) {
130 if (p->rightTree == NIL) {
131 return false;
132 }
133 return delete_child(p->rightTree, data);
134 } else if (p->value == data) {
135 if (p->rightTree == NIL) {
136 delete_one_child(p);
137 return true;
138 }
139 Node *smallest = getSmallestChild(p->rightTree);
140 swap(p->value, smallest->value);
141 delete_one_child(smallest);
142
143 return true;
144 }
145 }
146
147 void delete_one_child(Node *p) {
148 Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
149 if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL) {
150 p = NULL;
151 root = p;
152 return;
153 }
154
155 if (p->parent == NULL) {
156 delete p;
157 child->parent = NULL;
158 root = child;
159 root->color = BLACK;
160 return;
161 }
162
163 if (p->parent->leftTree == p) {
164 p->parent->leftTree = child;
165 } else {
166 p->parent->rightTree = child;
167 }
168 child->parent = p->parent;
169
170 if (p->color == BLACK) {
171 if (child->color == RED) {
172 child->color = BLACK;
173 } else
174 delete_case(child);
175 }
176
177 delete p;
178 }
179
180 void delete_case(Node *p) {
181 if (p->parent == NULL) {
182 p->color = BLACK;
183 return;
184 }
185 if (p->sibling()->color == RED) {
186 p->parent->color = RED;
187 p->sibling()->color = BLACK;
188 if (p == p->parent->leftTree)
189 rotate_left(p->sibling());
190 else
191 rotate_right(p->sibling());
192 }
193 if (p->parent->color == BLACK && p->sibling()->color == BLACK
194 && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
195 p->sibling()->color = RED;
196 delete_case(p->parent);
197 } else if (p->parent->color == RED && p->sibling()->color == BLACK
198 && p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK) {
199 p->sibling()->color = RED;
200 p->parent->color = BLACK;
201 } else {
202 if (p->sibling()->color == BLACK) {
203 if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
204 && p->sibling()->rightTree->color == BLACK) {
205 p->sibling()->color = RED;
206 p->sibling()->leftTree->color = BLACK;
207 rotate_right(p->sibling()->leftTree);
208 } else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
209 && p->sibling()->rightTree->color == RED) {
210 p->sibling()->color = RED;
211 p->sibling()->rightTree->color = BLACK;
212 rotate_left(p->sibling()->rightTree);
213 }
214 }
215 p->sibling()->color = p->parent->color;
216 p->parent->color = BLACK;
217 if (p == p->parent->leftTree) {
218 p->sibling()->rightTree->color = BLACK;
219 rotate_left(p->sibling());
220 } else {
221 p->sibling()->leftTree->color = BLACK;
222 rotate_right(p->sibling());
223 }
224 }
225 }
226
227 void insert(Node *p, int data) {
228 if (p->value >= data) {
229 if (p->leftTree != NIL)
230 insert(p->leftTree, data);
231 else {
232 Node *tmp = new Node();
233 tmp->value = data;
234 tmp->leftTree = tmp->rightTree = NIL;
235 tmp->parent = p;
236 p->leftTree = tmp;
237 insert_case(tmp);
238 }
239 } else {
240 if (p->rightTree != NIL)
241 insert(p->rightTree, data);
242 else {
243 Node *tmp = new Node();
244 tmp->value = data;
245 tmp->leftTree = tmp->rightTree = NIL;
246 tmp->parent = p;
247 p->rightTree = tmp;
248 insert_case(tmp);
249 }
250 }
251 }
252
253 void insert_case(Node *p) {
254 if (p->parent == NULL) {
255 root = p;
256 p->color = BLACK;
257 return;
258 }
259 if (p->parent->color == RED) {
260 if (p->uncle()->color == RED) {
261 p->parent->color = p->uncle()->color = BLACK;
262 p->grandparent()->color = RED;
263 insert_case(p->grandparent());
264 } else {
265 if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent) {
266 rotate_left(p);
267 rotate_right(p);
268 p->color = BLACK;
269 p->leftTree->color = p->rightTree->color = RED;
270 } else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent) {
271 rotate_right(p);
272 rotate_left(p);
273 p->color = BLACK;
274 p->leftTree->color = p->rightTree->color = RED;
275 } else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent) {
276 p->parent->color = BLACK;
277 p->grandparent()->color = RED;
278 rotate_right(p->parent);
279 } else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent) {
280 p->parent->color = BLACK;
281 p->grandparent()->color = RED;
282 rotate_left(p->parent);
283 }
284 }
285 }
286 }
287
288 void DeleteTree(Node *p) {
289 if (!p || p == NIL) {
290 return;
291 }
292 DeleteTree(p->leftTree);
293 DeleteTree(p->rightTree);
294 delete p;
295 }
296public:
297
298 bst() {
299 NIL = new Node();
300 NIL->color = BLACK;
301 root = NULL;
302 }
303
304 ~bst() {
305 if (root)
306 DeleteTree(root);
307 delete NIL;
308 }
309
310 void inorder() {
311 if (root == NULL)
312 return;
313 inorder(root);
314 cout << endl;
315 }
316
317 void insert(int x) {
318 if (root == NULL) {
319 root = new Node();
320 root->color = BLACK;
321 root->leftTree = root->rightTree = NIL;
322 root->value = x;
323 } else {
324 insert(root, x);
325 }
326 }
327
328 bool delete_value(int data) {
329 return delete_child(root, data);
330 }
331private:
332 Node *root, *NIL;
333};
B 树
B 树也是一种用于查找的平衡树,但是它又不是二叉树。
B 树的定义:B 树(B-tree)是一种树状数据结构,能够用来存储排序后的数据。这种数据结构能够让查找数据、循环存取、插入数据及删除的动作,都在对数时间内完成。B 树,概括来说是一个一般化的二叉查找树,可以拥有多于 2 个字结点。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree 算法减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。
在 B 树中查找给定关键字的方法是,首先把根结点取来,在根结点所包含的关键字 K1-Kn 查找给定的关键字(可用顺序查找或二分查找法),若找到等于给定值的关键字,则查找成功;否则,一定可以确定要查找的关键字在 Ki 与 Ki+1 之间,Pi 为指向子树根结点的指针,此时取指针 Pi 所指的结点继续查找,直至找到,或指针 Pi 为空时查找失败。
B 树作为一种多路搜索树(并不是二叉的):
- 定义任意非叶子结点最多只有 M 个儿子;且 M>2;
- 根结点的儿子树为[2,M];
- 除根结点以外的非叶子结点的儿子树为[M/2,M];
- 每个结点存放至少 M/2-1(取上整)和至多 M-1 个关键字;(至少两个关键字)
- 非叶子结点的关键字个数=指向儿子的指针个数-1;
- 非叶子结点的关键字:k[1],k[2],...,k[M-1];且 k[i]<k[i+1];
- 非叶子结点的指针:P[1], P[2], …, P[M];其中 P[1]指向关键字小于 K[1]的子树,P[M]指向关键字大于 K[M-1]的子树,其它 P[i]指向关键字属于(K[i-1], K[i])的子树;
- 所有叶子结点位于同一层;
B+ 树
B+ 树是 B 树的变体,也是一种多路搜索树
- 其定义基本与 B-树相同,除了:
- 非叶子结点的子树指针与关键字个数相同;
- 非叶子结点的子树指针 P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
- 为所有叶子结点增加一个链指针;
- 所有关键字都在叶子结点出现;
B+ 树的搜索与 B 树也基本相同,区别是 B+ 树只有达到叶子结点才命中(B 树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
B+ 树的性质
- 所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;
- 不可能在非叶子结点命中;
- 非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;
- 更适合文件索引系统。
B*树
B*树是 B+ 树的变体,在 B+ 树的非根和非叶子结点再增加指向兄弟的指针,将结点的最低利用率从 1/2 提高到 2/3。
B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为 2/3(代替 B+ 树的 1/2);
B+ 树的分裂:当一个结点满时,分配一个新的结点,并将原结点中 1/2 的数据复制到新结点,最后在父结点中增加新结点的指针;B+ 树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制 1/3 的数据到新结点,最后在父结点增加新结点的指针;
所以,B*树分配新结点的概率比 B+ 树要低,空间使用率更高。