适用组别:提高组
难度系数:8
一、二叉平衡树(Balanced Binary Tree)
又被称为AVL树(AVL是三个发明人名子的首子母)。
具有以下性质:
1、它是一棵二叉搜索树(binary search tree)。
2、它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1;
3、并且左右两个子树都是一棵平衡二叉树。
这个方案很好的解决了二叉查找树退化成链表的问题,把插入,查找,删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间,不过相对二叉查找树来说,时间上稳定了很多。
二、理想平衡与适度平衡
理想平衡就是左子树和右子树的高度一样,适度平衡就是放松平衡标准,大体上平衡就可以。
例如:AVL树的左右子树高差不大于1。
三、调平衡
找到最小不平衡子树,从这个树的根a开始调整
把需要重新平衡的结点叫做α,由于任意两个结点最多只有两个儿子,因此高度不平衡时,α结点的两颗子树的高度相差2.容易看出,这种不平衡可能出现在下面4中情况中:
1. α的左子树的左子树
2. α的左子树的右子树
3. α的右子树的左子树
4. α的右子树的右子树
调整平衡
四、插入
1、如果平衡二叉树为空,则创建新节点
2、如果node->data=x,已经存在x,什么也不做
3、如果x< node-data,插入到左子树,否则插入到右子树
4、调平衡
五、删除操作
同插入操作一样,删除结点时也有可能破坏平衡性,这就要求我们删除的时候要进行平衡性调整。
1、如果平衡二叉树为空,则什么也不做。
2、如果node->data==x,找到要删除结点,如果node有一个孩子,让孩子顶替,否则令其直接前驱(或者直接后继)代替。然后删除其直接前驱(或直接后继)
3、如果x<node->data,到左子树查找并删除,否则到右子树查找删除
4、重新调整平衡
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 | /**************************************************************** * Description: C++ implementation of self balancing binary search tree * Author: Alex Li * Date: 2023-06-27 18:16:01 * LastEditTime: 2023-06-29 16:24:48 ****************************************************************/ #include <iostream> using namespace std; //结点结构体,一个数据域,一个高度域,两个指针域,分别指向左右结点 struct Node{ int data; int height; struct Node *left; struct Node *right; }; //计算高度 int Height(Node *N){ if(N!=NULL)return N->height; else return 0; } //更新高度 void UpdateHeight(Node *N){ if(N!=NULL)N->height =max(Height(N->left),Height(N->right))+1; else return; } // 创建新结点 Node *newNode(int data) { Node *node = new Node(); node->data = data; node->left = NULL; node->right = NULL; node->height = 1; return node; } // left left rotation 左左旋转 Node *LL_Rotate(Node *y) { Node *x = y->left; y->left = x->right; x->right = y; UpdateHeight(y); UpdateHeight(x); //x基于y计算高度,所以必须先算y return x; } // right right rotaion 右右旋转 Node *RR_Rotate(Node *y) { Node *x = y->right; y->right=x->left; x->left =y; UpdateHeight(y); UpdateHeight(x);//x基于y计算高度,所以必须先算y return x; } // left right rotaion 左右旋转 Node *LR_Rotate(Node *y){ Node *x=y->left->right; //Node *z=y->left; y->left->right=x->left; x->left=y->left; y->left=x->right; x->right=y; return x; //可以用下面丙行代码替代上面代码。 // y->left= RR_Rotate(y->left); // return LL_Rotate(y); } Node *RL_rotate(Node *y){ Node *x=y->right->left; y->right->left=x->right; x->left=y->right; y->right=x->right; x->left=y; return x; ////可以用下面丙行代码替代上面代码。 // y->right= LL_Rotate(y->right); // return RR_Rotate(y); } // Get the balance factor of each node int getBalanceFactor(Node *N) { if (N == NULL) return 0; return Height(N->left) -Height(N->right); } Node *AdjustBalance(Node *node){ if(node==NULL)return node; int balanceFactor = getBalanceFactor(node); if (balanceFactor > 1) {//沿着高的哪棵子树调整 if(Height(node->left->left)>=Height(node->left->right)) node=LL_Rotate(node); else node=LR_Rotate(node); } else if (balanceFactor < -1) { if (Height(node->right->right)>=Height(node->right->left)) node=RR_Rotate(node); else node=RL_rotate(node); } return node; } // Insert a node Node *insertNode(Node *node, int data) { // Find the correct postion and insert the node if (node == NULL){ node=newNode(data); return node; } if (data < node->data) node->left = insertNode(node->left, data); else if(data>node->data) node->right = insertNode(node->right, data); // Update the balance factor of each node and // balance the tree UpdateHeight(node); node=AdjustBalance(node); return node; } // Delete a node Node *DeleteNode(Node *node, int data) { if(node==NULL)return node; if(node->data==data){ //找到要删除的节点 if(!node->left||!node->right){ //如果有一个孩子为空,子承父业 Node *temp=node; node=(node->left)?node->left:node->right; delete temp; } else{ //选其直接前驱(也就是左子树的最右节点)代替,然后删除其直接前驱 Node *temp; temp=node->left; while(temp->right)temp=temp->right; node->data=temp->data; node->left=DeleteNode(node->left,node->data); } } else if(node->data>data) node->left=DeleteNode(node->left,data); //在左子树中删除 else node->right=DeleteNode(node->right,data); //在右子树中删除 UpdateHeight(node); node=AdjustBalance(node); return node; } //前序遍历查看结果 void Inorder(Node *node){ if(node==NULL) return ; Inorder(node->left); cout<<node->data<<"\t"<<node->height<<endl; Inorder(node->right); } int main() { Node *node = NULL; node = insertNode(node, 33); node = insertNode(node, 13); node = insertNode(node, 53); node = insertNode(node, 9); node = insertNode(node, 21); node = insertNode(node, 61); node = insertNode(node, 8); node = insertNode(node, 11); node = insertNode(node,7); Inorder(node); node = DeleteNode(node, 61); cout << "After deleting " << endl; Inorder(node); } |
I9633,P3369