6 #include <rudiments/stdio.h> 7 #include <rudiments/private/nodeinlines.h> 9 #define AVLTREE_TEMPLATE template <class valuetype> 11 #define AVLTREE_CLASS avltree<valuetype> 13 #define AVLTREENODE_TEMPLATE template <class valuetype> 15 #define AVLTREENODE_CLASS avltreenode<valuetype> 19 AVLTREE_CLASS::avltree() {
28 AVLTREE_CLASS::~avltree() {
34 void AVLTREE_CLASS::insert(valuetype value) {
48 stdoutput.
printf(
"----------------------------------------" 49 "---------------------------------------\n");
55 top->insert(node,&top);
59 first->getLeftChild();
60 first=first->getLeftChild()) {}
64 last->getRightChild();
65 last=last->getRightChild()) {}
89 stdoutput.
printf(
"----------------------------------------" 90 "---------------------------------------\n");
114 bool AVLTREE_CLASS::remove(valuetype value) {
116 return (current)?
remove(current):
false;
121 bool AVLTREE_CLASS::removeAll(valuetype value) {
123 while (
remove(value)) {
138 uint64_t AVLTREE_CLASS::getLength()
const {
171 return (node)?node->
getNext():NULL;
187 stdoutput.
printf(
"find ");
189 stdoutput.
printf(
" from ");
193 node_print(
"(null)");
202 int32_t result=current->
compare(value);
207 stdoutput.
printf(
" - %d\n",result);
212 }
else if (result==0) {
214 }
else if (result>0) {
221 stdoutput.
printf(
" success!\n");
223 stdoutput.
printf(
" failed\n");
225 stdoutput.
printf(
"} find\n\n");
241 void AVLTREE_CLASS::clear() {
245 stdoutput.
printf(
"clearing %d nodes {\n",length);
249 AVLTREENODE_CLASS *node=top;
253 if (node->getRightChild()) {
254 node=node->getRightChild();
256 while (node->getLeftChild()) {
257 node=node->getLeftChild();
261 AVLTREENODE_CLASS *p=node->getParent();
263 if (p->getLeftChild()==node) {
264 p->setLeftChild(NULL);
266 p->setRightChild(NULL);
272 stdoutput.
printf(
" clearing %lld\n",i);
287 stdoutput.
printf(
"} cleared %d nodes\n\n",i);
299 void AVLTREE_CLASS::clearAndDelete() {
303 stdoutput.
printf(
"clearing %d nodes {\n",length);
307 AVLTREENODE_CLASS *node=top;
311 if (node->getRightChild()) {
312 node=node->getRightChild();
314 while (node->getLeftChild()) {
315 node=node->getLeftChild();
319 AVLTREENODE_CLASS *p=node->getParent();
321 if (p->getLeftChild()==node) {
322 p->setLeftChild(NULL);
324 p->setRightChild(NULL);
330 stdoutput.
printf(
" clearing %lld\n",i);
333 delete node->getValue();
341 stdoutput.
printf(
"} cleared %d nodes\n\n",i);
353 void AVLTREE_CLASS::clearAndArrayDelete() {
357 stdoutput.
printf(
"clearing %d nodes {\n",length);
361 AVLTREENODE_CLASS *node=top;
365 if (node->getRightChild()) {
366 node=node->getRightChild();
368 while (node->getLeftChild()) {
369 node=node->getLeftChild();
373 AVLTREENODE_CLASS *p=node->getParent();
375 if (p->getLeftChild()==node) {
376 p->setLeftChild(NULL);
378 p->setRightChild(NULL);
384 stdoutput.
printf(
" clearing %lld\n",i);
387 delete[] node->getValue();
395 stdoutput.
printf(
"} cleared %d nodes\n\n",i);
407 void AVLTREE_CLASS::print()
const {
415 AVLTREENODE_CLASS::avltreenode(valuetype value) {
426 AVLTREENODE_CLASS::~avltreenode() {
431 void AVLTREENODE_CLASS::setValue(valuetype value) {
437 valuetype AVLTREENODE_CLASS::getValue()
const {
443 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getParent() {
449 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getLeftChild() {
455 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getRightChild() {
461 uint8_t AVLTREENODE_CLASS::getLeftHeight() {
467 uint8_t AVLTREENODE_CLASS::getRightHeight() {
473 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getPrevious() {
483 AVLTREENODE_CLASS *node=left;
486 while (node->right) {
495 if (parent->right==
this) {
502 AVLTREENODE_CLASS *node=parent;
507 if (node->parent->right==node) {
518 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getNext() {
528 AVLTREENODE_CLASS *node=right;
540 if (parent->left==
this) {
547 AVLTREENODE_CLASS *node=parent;
552 if (node->parent->left==node) {
563 int32_t AVLTREENODE_CLASS::compare(valuetype value)
const {
564 return node_compare(this->value,value);
570 return node_compare(this->value,peer->value);
575 void AVLTREENODE_CLASS::print()
const {
576 uint16_t indentlevel=0;
577 print(
"top",&indentlevel);
582 void AVLTREENODE_CLASS::print(
const char *name, uint16_t *indentlevel)
const {
584 for (uint16_t i=0; i<*indentlevel; i++) {
587 stdoutput.
printf(
"<%s value=\"",name);
589 stdoutput.
printf(
"\" lh=\"%d\" rh=\"%d\" bf=\"%d\"",
590 leftheight,rightheight,leftheight-rightheight);
591 if (!left && !right) {
597 left->print(
"left ",indentlevel);
600 right->print(
"right",indentlevel);
603 for (uint16_t i=0; i<*indentlevel; i++) {
606 stdoutput.
printf(
"</%s>\n",name);
612 void AVLTREENODE_CLASS::setParent(AVLTREENODE_CLASS *node) {
618 void AVLTREENODE_CLASS::setLeftChild(AVLTREENODE_CLASS *node) {
624 void AVLTREENODE_CLASS::setRightChild(AVLTREENODE_CLASS *node) {
642 if (node->
compare(location->value)<=0) {
644 if (location->left) {
645 location=location->left;
649 stdoutput.
printf(
"insert ");
650 node_print(node->value);
651 stdoutput.
printf(
" to left of ");
652 node_print(location->value);
653 stdoutput.
printf(
" {\n\n");
656 location->setLeftChild(node);
660 }
else if (node->
compare(location->value)>0) {
662 if (location->right) {
663 location=location->right;
667 stdoutput.
printf(
"insert ");
668 node_print(node->value);
669 stdoutput.
printf(
" to right of ");
670 node_print(location->value);
671 stdoutput.
printf(
" {\n\n");
674 location->setRightChild(node);
680 node->setParent(location);
683 adjustParentHeights(node);
686 node->parent->balance(treetop);
689 stdoutput.
printf(
"} insert\n\n");
698 stdoutput.
printf(
"detach ");
700 stdoutput.
printf(
" {\n\n");
703 while (top->parent) { top=top->parent; }
712 stdoutput.
printf(
"less simple case: 2 children\n\n");
724 while (successor->left) {
725 successor=successor->left;
729 stdoutput.
printf(
"swap ");
731 stdoutput.
printf(
" and ");
732 node_print(successor->value);
739 bool successorwasimmediaterightchild=(right==successor);
748 successor->parent=parent;
749 if (successor->parent) {
750 if (successor->parent->left==
this) {
751 successor->parent->left=successor;
753 successor->parent->right=successor;
761 successor->left=left;
762 if (successor->left) {
763 successor->left->parent=successor;
765 if (successorwasimmediaterightchild) {
766 successor->right=
this;
767 successor->right->parent=successor;
769 successor->right=right;
770 if (successor->right) {
771 successor->right->parent=successor;
776 if (parent->left==successor) {
785 successor->leftheight=leftheight;
786 successor->rightheight=rightheight;
802 leftheight=temp.leftheight;
803 rightheight=temp.rightheight;
807 while (top->parent) { top=top->parent; }
818 stdoutput.
printf(
"simple case: 1 or 0 children\n\n");
836 if (parent->left==
this) {
838 parent->leftheight--;
841 parent->rightheight--;
846 child->parent=parent;
856 adjustParentHeights(p);
879 while (top->parent) { top=top->parent; }
885 stdoutput.
printf(
"} detach\n\n");
894 while (node->parent) {
897 uint8_t height=((node->leftheight>node->rightheight)?
899 node->rightheight)+1;
907 if (node->parent->left==node) {
908 if (node->parent->leftheight==height) {
911 node->parent->leftheight=height;
913 if (node->parent->rightheight==height) {
916 node->parent->rightheight=height;
931 stdoutput.
printf(
"balance at ");
933 stdoutput.
printf(
" {\n\n");
936 while (top->parent) { top=top->parent; }
946 if ((node->leftheight>node->rightheight &&
947 node->leftheight-node->rightheight>1) ||
948 (node->rightheight>node->leftheight &&
949 node->rightheight-node->leftheight>1)) {
952 stdoutput.
printf(
"imbalance at ");
953 node_print(node->value);
960 if (node->rightheight>node->leftheight) {
961 if (node->right->rightheight>
962 node->right->leftheight) {
963 node=node->leftRotate(treetop);
965 node=node->rightLeftRotate(treetop);
967 }
else if (node->leftheight>node->rightheight) {
968 if (node->left->leftheight>
969 node->left->rightheight) {
970 node=node->rightRotate(treetop);
972 node=node->leftRightRotate(treetop);
978 while (top->parent) { top=top->parent; }
985 stdoutput.
printf(
"no imbalance at ");
986 node_print(node->value);
997 stdoutput.
printf(
"continuing at ");
998 node_print(node->value);
1005 #ifdef DEBUG_AVLTREE 1006 stdoutput.
printf(
"} balance\n\n");
1027 #ifdef DEBUG_AVLTREE 1028 stdoutput.
printf(
"left rotation at ");
1030 stdoutput.
printf(
"\n\n");
1037 uint8_t starheight=b->leftheight;
1048 #ifdef DEBUG_AVLTREE 1049 stdoutput.
printf(
"(new tree top)\n\n");
1053 b->parent=a->parent;
1059 a->rightheight=starheight;
1067 adjustParentHeights(a);
1093 #ifdef DEBUG_AVLTREE 1094 stdoutput.
printf(
"right-left rotation at ");
1096 stdoutput.
printf(
" {\n\n");
1097 stdoutput.
printf(
"right part\n\n");
1107 uint8_t starheight=b->rightheight;
1117 c->leftheight=starheight;
1125 adjustParentHeights(c);
1127 #ifdef DEBUG_AVLTREE 1129 while (top->parent) { top=top->parent; }
1134 leftRotate(treetop);
1136 #ifdef DEBUG_AVLTREE 1137 stdoutput.
printf(
"} right-left\n\n");
1163 #ifdef DEBUG_AVLTREE 1164 stdoutput.
printf(
"right rotation at ");
1166 stdoutput.
printf(
"\n\n");
1173 uint8_t starheight=b->rightheight;
1184 #ifdef DEBUG_AVLTREE 1185 stdoutput.
printf(
"(new tree top)\n\n");
1189 b->parent=c->parent;
1195 c->leftheight=starheight;
1203 adjustParentHeights(c);
1229 #ifdef DEBUG_AVLTREE 1230 stdoutput.
printf(
"left-right rotation at ");
1232 stdoutput.
printf(
" {\n\n");
1233 stdoutput.
printf(
"left part\n\n");
1243 uint8_t starheight=b->leftheight;
1253 a->rightheight=starheight;
1261 adjustParentHeights(a);
1263 #ifdef DEBUG_AVLTREE 1265 while (top->parent) { top=top->parent; }
1270 rightRotate(treetop);
1272 #ifdef DEBUG_AVLTREE 1273 stdoutput.
printf(
"} left-right\n\n");
int32_t compare(valuetype value) const
avltreenode< valuetype > * getNext()
avltreenode< valuetype > * getLeftChild()
size_t printf(const char *format,...)
avltreenode< valuetype > * getPrevious()
avltreenode< valuetype > * getRightChild()
valuetype getValue() const