AVL树实现代码

dinghj 2013-09-15

展开全文

一棵AVL树是一棵平衡树，除了二叉查找树的性质外，还有这个性质：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。关于二叉查找树、AVL树、红黑树的性质及实现，详见博客：http://blog.sina.com.cn/s/blog_62186b460101a2m4.html

[代码] AVL

001 #ifndef AVLTree_H

002 #define AVLTree_H

003

004 #include <stack>

005 using namespace std;

006

007 #define MAX(a,b) (a > b ? a : b)

008

009

010 template<typename T>

011 class TreeNode

012 {

013 public:

014 T value; // value contained in the node

015 TreeNode<T> * parent; // Pointer to the parent

016 TreeNode<T> * left; // Pointer to the left child

017 TreeNode<T> * right; // Pointer to the right child

018 int height;

019

020 TreeNode() // No-arg constructor

021 {

022 left = NULL;

023 right = NULL;

024 parent = NULL;

025 height = 0;

026 }

027

028 TreeNode(T value) // Constructor

029 {

030 this->value = value;

031 left = NULL;

032 right = NULL;

033 parent = NULL;

034 height = 0;

035 }

036 };

037

038

039 template < typename T >

040 class AVLTree

041 {

042 public:

043 int treeSize;

044 AVLTree();

045 AVLTree(T values[],int arraySize);

046 int insert(T value);

047 void inOrder();

048 void inOrderNorRec();

049 int deleteNode(T value);

050 int successor(T value);

051 int predecessor(T value);

052 int maxValue();

053 int minValue();

054 int getSize(T value);

055 void output();

056

057 private:

058 TreeNode<T> * treeroot;

059 void LeftRotate(TreeNode<T> * target);

060 void RightRotate(TreeNode<T> * target);

061 void LeftRightRotate(TreeNode<T> * target);

062 void RightLeftRotate(TreeNode<T> * target);

063 int insert(TreeNode<T> * targetParent,TreeNode<T> * target,T value);

064 void inOrder(TreeNode<T> *target);

065 void inOrderNorRec(TreeNode<T> *target);

066 TreeNode<T> * search(T searchvalue);

067 int deleteNode(TreeNode<T> *target,T value);

068 TreeNode<T> * successor(TreeNode<T> *target);

069 TreeNode<T> * predecessor(TreeNode<T> *target);

070 TreeNode<T> * maxValue(TreeNode<T> *target);

071 TreeNode<T> * minValue(TreeNode<T> *target);

072 int Height(TreeNode<T> *target);

073 int getSize(TreeNode<T> *target);

074 void output(TreeNode<T> *target,int totalSpaces);

075 };

076

077

078 template < typename T >

079 AVLTree<T>::AVLTree()

080 {

081 treeroot = NULL;

082 treeSize = 0;

083 }

084

085

086 template < typename T >

087 AVLTree<T>::AVLTree(T values[],int arraySize)

088 {

089 treeroot = NULL;

090 treeSize = 0;

091 for(int i=0 ; i<arraySize ; i++){

092 insert(treeroot,treeroot,values[i]);

093 }

094 }

095

096

097 template< typename T >

098 void AVLTree<T>::LeftRotate(TreeNode<T> * target)

099 {

100 TreeNode<T> *rightchild = target->right;

101 target->right = rightchild->left;

102 if (rightchild->left != NULL){

103 rightchild->left->parent = target;

104 }

105

106 if (target->parent == NULL){

107 treeroot = rightchild;

108 rightchild->parent = NULL;

109 }else if(target->parent->left == target){

110 target->parent->left = rightchild;

111 rightchild->parent = target->parent;

112 }else{

113 target->parent->right = rightchild;

114 rightchild->parent = target->parent;

115 }

116

117 rightchild->left = target;

118 target->parent = rightchild;

119

120 int leftHeight = Height(target->left);

121 int RightHeight = Height(target->right);

122 target->height = MAX(leftHeight,RightHeight) + 1;

123

124 leftHeight = Height(rightchild->left);

125 RightHeight = Height(rightchild->right);

126 rightchild->height = MAX(leftHeight,RightHeight) + 1;

127 }

128

129

130 template< typename T >

131 void AVLTree<T>::RightRotate(TreeNode<T> * target)

132 {

133 {

134 TreeNode<T> *leftchild = target->left;

135 target->left = leftchild->right;

136 if (leftchild->right != NULL){

137 leftchild->left->parent = target;

138 }

139

140 if (target->parent == NULL){

141 treeroot = leftchild;

142 leftchild->parent = NULL;

143 }else if(target->parent->left == target){

144 target->parent->left = leftchild;

145 leftchild->parent = target->parent;

146 }else{

147 target->parent->right = leftchild;

148 leftchild->parent = target->parent;

149 }

150

151 leftchild->right = target;

152 target->parent = leftchild;

153

154 int leftHeight = Height(target->left);

155 int RightHeight = Height(target->right);

156 target->height = MAX(leftHeight,RightHeight) + 1;

157

158 leftHeight = Height(leftchild->left);

159 RightHeight = Height(leftchild->right);

160 leftchild->height = MAX(leftHeight,RightHeight) + 1;

161 }

162 }

163

164

165 template< typename T >

166 void AVLTree<T>::LeftRightRotate(TreeNode<T> * target)

167 {

168 LeftRotate(target->left);

169 RightRotate(target);

170 }

171

172

173 template< typename T >

174 void AVLTree<T>::RightLeftRotate(TreeNode<T> * target)

175 {

176 RightRotate(target->right);

177 LeftRotate(target);

178 }

179

180

181 template <typename T>

182 int AVLTree<T>::insert(T value)

183 {

184 this->insert(treeroot,treeroot,value);

185 return 0;

186 }

187

188

189 template <typename T>

190 int AVLTree<T>::insert(TreeNode<T> * targetParent,TreeNode<T> * target,T value)

191 {

192 if (target == NULL){

193 target = new TreeNode<T>(value);

194 if (targetParent == NULL){

195 this->treeroot = target;

196 }else{

197 target->parent = targetParent;

198 if (targetParent->value > value){

199 targetParent->left = target;

200 }else{

201 targetParent->right = target;

202 }

203 }

204 this->treeSize++;

205 return 0;

206 }

207 else if(target->value > value){

208 this->insert(target,target->left,value);

209 if(this->Height(target->left) - this->Height(target->right) >= 2){

210 if(target->left->value > value){

211 this->RightRotate(target);

212 }

213 else{

214 this->LeftRightRotate(target);

215 }

216 }

217 }

218 else if(target->value < value){

219 this->insert(target,target->right,value);

220 if(this->Height(target->right) - this->Height(target->left) >= 2){

221 if(target->right->value < value){

222 this->LeftRotate(target);

223 }

224 else{

225 this->RightLeftRotate(target);

226 }

227 }

228 }else{

229 return 1;

230 }

231

232 int leftHeight = Height(target->left);

233 int RightHeight = Height(target->right);

234 target->height = MAX(leftHeight,RightHeight) + 1;

235 return 0;

236 }

237

238

239 template <typename T>

240 TreeNode<T> * AVLTree<T>::search(T searchvalue)

241 {

242 TreeNode<T> *current = this->treeroot;

243 int find =0;

244 while (current != NULL && find == 0){

245 if (current->value == searchvalue){

246 find = 1;

247 }

248 else if(current->value > searchvalue){

249 current = current->left;

250 }else{

251 current = current->right;

252 }

253 }

254

255 if (find == 1){

256 return current;

257 }else{

258 return NULL;

259 }

260 }

261

262

263 template <typename T>

264 int AVLTree<T>::deleteNode(T value){

265 TreeNode<T> *delNode = this->search(value);

266 if ( delNode == NULL){

267 cout << "not find " << endl;

268 return 1;

269 }

270 this->deleteNode(this->treeroot,value);

271 cout << "Node "<< value <<" has been deleted."<< endl;

272 return 0;

273 }

274

275

276 template <typename T>

277 int AVLTree<T>::deleteNode(TreeNode<T> *target,T value){

278 if(target->value > value) deleteNode(target->left,value);

279 else if(target->value < value) deleteNode(target->right,value);

280 else if(target->left != NULL)

281 {

282 target->value = this->maxValue(target->left)->value;

283 deleteNode(target->left,target->value);

284 }

285 else if(target->right != NULL)

286 {

287 target->value = this->minValue(target->right)->value;

288 deleteNode(target->right,target->value);

289 }

290 else

291 {

292 if(target->parent->left == target){

293 target->parent->left = NULL;

294 }else{

295 target->parent->right = NULL;

296 }

297 delete target;

298 this->treeSize--;

299 return 0;

300 }

301

302 int leftHeight = Height(target->left);

303 int RightHeight = Height(target->right);

304 target->height = MAX(leftHeight,RightHeight) + 1;

305 if (RightHeight - leftHeight >= 2)

306 {

307 if(target->right->right==NULL)

308 {

309 this->RightLeftRotate(target);

310 }

311 else

312 {

313 this->LeftRotate(target);

314 }

315 }

316 else if(leftHeight - RightHeight >= 2)

317 {

318 if(target->left->left == NULL)

319 {

320 this->LeftRightRotate(target);

321 }

322 else

323 {

324 this->RightRotate(target);

325 }

326 }

327

328 return 0;

329 }

330

331

332 template <typename T>

333 int AVLTree<T>::successor(T value)

334 {

335 TreeNode<T> *position = this->search(value);

336 if ( position == NULL){

337 cout << "not find " << endl;

338 return 1;

339 }

340 TreeNode<T> *successorNode = this->successor(position);

341 if ( successorNode != NULL)

342 cout << value << " \'s successor is:" << successorNode->value << endl;

343 else

344 cout << value << " has no successor" << endl;

345 return 0;

346 }

347

348

349 template <typename T>

350 TreeNode<T> * AVLTree<T>::successor(TreeNode<T> *target)

351 {

352 if ( target->right != NULL){

353 return minValue(target->right);

354 }

355 TreeNode<T> * parentNode =target->parent;

356 while ( parentNode != NULL && parentNode->right == target){

357 target = parentNode;

358 parentNode = parentNode->parent;

359 }

360 return parentNode;

361 }

362

363

364 template <typename T>

365 int AVLTree<T>::predecessor(T value)

366 {

367 TreeNode<T> *position = this->search(value);

368 if ( position == NULL){

369 cout << "Can\'t find " << value <<" in AVL tree." <<endl;

370 return 1;

371 }

372 TreeNode<T> *predecessorNode = this->predecessor(position);

373 if ( predecessorNode != NULL)

374 cout << value << " \'s predecessor is:" << predecessorNode->value << endl;

375 else

376 cout << value << " has no predecessor" << endl;

377 return 0;

378 }

379

380

381 template <typename T>

382 TreeNode<T> * AVLTree<T>::predecessor(TreeNode<T> *target)

383 {

384 if ( target->left != NULL){

385 return maxValue(target->left);

386 }

387 TreeNode<T> * parentNode =target->parent;

388 while ( parentNode != NULL && parentNode->left == target){

389 target = parentNode;

390 parentNode = parentNode->parent;

391 }

392 return parentNode;

393 }

394

395

396 template <typename T>

397 int AVLTree<T>::maxValue()

398 {

399 TreeNode<T> * max = this->maxValue(treeroot);

400 return max->value;

401 }

402

403

404 template <typename T>

405 TreeNode<T> * AVLTree<T>::maxValue(TreeNode<T> *target)

406 {

407 while (target -> right != NULL){

408 target = target -> right;

409 }

410 return target;

411 }

412

413

414 template <typename T>

415 int AVLTree<T>::minValue()

416 {

417 TreeNode<T> * min = this->minValue(treeroot);

418 return min->value;

419 }

420

421

422 template <typename T>

423 TreeNode<T> * AVLTree<T>::minValue(TreeNode<T> *target)

424 {

425 while (target -> left != NULL){

426 target = target -> left;

427 }

428 return target;

429 }

430

431

432 template <typename T>

433 int AVLTree<T>::getSize(T value)

434 {

435 TreeNode<T> *target = this->search(value);

436 return getSize(target);

437 }

438

439

440 template <typename T>

441 int AVLTree<T>::getSize(TreeNode<T> *target)

442 {

443 if (target == NULL){

444 return 0;

445 }

446

447 if (target->left == NULL && target->left == NULL){

448 return 1;

449 }else {

450 return this->getSize(target->left) + 1 + this->getSize(target->right);

451 }

452 }

453

454

455 template <typename T>

456 void AVLTree<T>::inOrder()

457 {

458 inOrder(treeroot);

459 cout << endl;

460 }

461

462

463 template <typename T>

464 void AVLTree<T>::inOrder(TreeNode<T> *target)

465 {

466 if (target == NULL)

467 return ;

468 inOrder(target->left);

469 cout << target->value << " ";

470 inOrder(target->right);

471 }

472

473

474 template <typename T>

475 void AVLTree<T>::inOrderNorRec()

476 {

477 inOrderNorRec(treeroot);

478 cout << endl;

479 }

480

481

482 template <typename T>

483 void AVLTree<T>::inOrderNorRec(TreeNode<T> *target)

484 {

485 stack < TreeNode<T> *> s;

486 while ((target != NULL) || !s.empty())

487 {

488 if (target != NULL)

489 {

490 s.push(target);

491 target = target->left;

492 }

493 else

494 {

495 target = s.top();

496 cout << target->value << " ";

497 s.pop();

498 target = target->right;

499 }

500 }

501 }

502

503

504 template< typename T >

505 int AVLTree<T>::Height(TreeNode<T> *target)

506 {

507 return target == NULL ? -1 : target->height;

508 }

509

510

511 template <typename T>

512 void AVLTree<T>::output()

513 {

514 output(treeroot,0);

515 }

516

517

518 template <typename T>

519 void AVLTree<T>::output(TreeNode<T> *target,int totalSpaces)

520 {

521 if(target != NULL)

522 {

523 output(target->right,totalSpaces+4);

524 for(int i=0;i<totalSpaces;i++){

525 cout<<' ';

526 }

527 if (target->parent != NULL){

528 cout << target->value << "[" << target->parent->value << "]" << endl;

529 }

530 else{

531 cout << target->value << "[ROOT]" << endl;

532 }

533 output(target->left,totalSpaces+4);

534 }

535 };

536

537 #endif

本站是提供个人知识管理的网络存储空间，所有内容均由用户发布，不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息，谨防诈骗。如发现有害或侵权内容，请点击一键举报。

转藏分享

QQ空间 QQ好友新浪微博微信

献花（0） +1

来自： dinghj > 《算法编程》

举报/认领

0条评论

发表

请遵守用户评论公约

类似文章 更多

dinghj

关注对话

TA的最新馆藏

利用page rank,hits算法实现的一个简单的文本摘要系统
用graphviz,pygraphviz快速自动绘图
利用pygraphviz绘制二叉树
[转] 法国画家delphinenjolras【绝品收藏】
艾菲：你以为做的是投资，其实只是在赌博！
凌落辰：从几道题中看到的股市哲思

喜欢该文的人也喜欢更多

热门阅读换一换