东营网站搭建,自己做的网站如何上传,珠海本地网站,子页面的网站地址怎么做AVL简称平衡二叉树#xff0c;缩写为BBST#xff0c;由苏联数学家 Adelse-Velskil 和 Landis 在 1962 年提出。
二叉树是动态查找的典范#xff0c;但在极限情况下#xff0c;二叉树的查找效果等同于链表#xff0c;而平衡二叉树可以完美的达到 log 2 n \log_2 n log2…AVL简称平衡二叉树缩写为BBST由苏联数学家 Adelse-Velskil 和 Landis 在 1962 年提出。
二叉树是动态查找的典范但在极限情况下二叉树的查找效果等同于链表而平衡二叉树可以完美的达到 log 2 n \log_2 n log2n。
一直想深入的研究一下并手写平衡二叉树的插入、删除代码。
可惜的是国内数据结构的神级教材阎蔚敏老师主编《数据结构》一书中并未看到关于AVL树的代码。
例子
将17921214263315402325一次插入到一棵初始化为空的AVL树中画出该二叉平衡树。
解过程和结果如下图所示。 所谓平衡二叉树就是指二叉树的左、右子树的深度差不超过2。每当插入一个新的元素导致左右子树的深度超过2层时需要对二叉树的失衡节点进行平衡保持左右子树高度差在-1到1之间。
可以使用两个整数来表示左右子树的深度前面一个表示左子树的层数右边一个代表右子树的层数。
调整时首先需要找到要平衡的节点。找到调整节点后处理的方法有4种
上图中圆标号1的是左-左结构标号2的是左-右结构标号3的是右-右标号4的是右-左结构这4种结构的处理方式各有不同。
左-左结构即(21)结构
中间节点当作父节点最上面的节点当作右节点最下边节点当作左节点
左-右结构即(2-1)结构
最下面节点当作父节点父节点当作右节点中间节点当作左节点
右-右结构即(-2-1)结构
中间节点当作父节点最上面的节点当作左节点最下边节点当作右节点
右-左结构即(-21)结构
最下面节点当作父节点最上面节点当作左节点中间节点当作右节点
编程中计算左、右子树深度的代码如下 int deep(BBST* b) {if (b 0){return 0;}int ld deep(b-lchild);int rd deep(b-rchild) ;return ld rd ? ld 1 : rd 1;
}
有了上面的理论和编程基础我们可以慢慢的调试并手动写出平衡二叉树的插入代码
int BBSTree::insert(ELEMENT* e) {if (mTree 0){mTree newnode(e);mSize 1;return 1;}BBST* t mTree;BBST* tc 0;Stack s;ELEMENT elem;while (1) {if (e-e t-data.e) {return 0;}else if (e-e t-data.e){if (t-rchild 0){tc newnode(e);tc-parent t;t-rchild tc;mSize;break;}else { elem.e (unsigned long long)t;s.push((ELEMENT*)elem);t t-rchild; }}else {if (t-lchild 0){tc newnode(e);tc-parent t;t-lchild tc;mSize;break;}else {elem.e (unsigned long long)t;s.push((ELEMENT*)elem);t t-lchild; }}}while (s.isEmpty() 0) {s.pop(elem);BBST* b (BBST*)elem.e;b-ld deep(b-lchild);b-rd deep(b-rchild);t-ld deep(t-lchild);t-rd deep(t-rchild);int high_diff b-ld - b-rd;int low_diff t-ld - t-rd;if(high_diff 2 low_diff 1){BBST* f (BBST*)b-parent;if (ff-lchild b){f-lchild t;}else if (ff-rchild b){f-rchild t;}t-parent f;BBST* tr t-rchild;t-rchild b;b-parent t;b-lchild tr;if (tr){tr-parent b;}if (b mTree){mTree t;}}else if (high_diff 2 low_diff -1){BBST* f (BBST*)b-parent;if (f-lchild b){f-lchild tc;}else if (f-rchild b){f-rchild tc;}tc-parent f;t-parent tc;if (tc-lchild){tc-lchild-parent t;}t-rchild tc-lchild;b-parent tc;if (tc-rchild){tc-rchild-parent b;}b-lchild tc-rchild;tc-rchild b;tc-lchild t; if (b mTree){mTree tc;}}else if (high_diff -2 low_diff 1){BBST* f (BBST*)b-parent;if (ff-lchild b){f-lchild tc;}else if (ff-rchild b){f-rchild tc;}tc-parent f;b-parent tc;b-rchild tc-lchild;if (tc-lchild){tc-lchild-parent b;}t-parent tc;t-lchild tc-rchild;if (tc-rchild){tc-rchild-parent t;}tc-rchild t;tc-lchild b;if (b mTree){mTree tc;}}else if (high_diff -2 low_diff -1){BBST* f (BBST*)b-parent;if (f f-lchild b){f-lchild t;}else if (f f-rchild b){f-rchild t;}t-parent f;BBST* tl t-lchild;t-lchild b;b-parent t;b-rchild tl;if (tl){tl-parent b;}if (b mTree){mTree t;}}tc t;t b;}return 0;
}
完整代码地址 https://github.com/satadriver/dataStruct
