二叉排序树 插入 数据结构与算法（二）:线性表、栈、树(二叉树，AVL树)、图(4)

parent.left = current.right;

} else {

parent.right = current.right;

}

}

} else { // 考虑第二种情况

TreeNode<E> parentOfRightMost = current;

TreeNode<E> rightMost = current.left;

// 找到左子树中最大的元素节点

while (rightMost.right != null) {

parentOfRightMost = rightMost;

rightMost = rightMost.right;

}

// 替换

current.element = rightMost.element;

// parentOfRightMost和rightMost左孩子相连

if (parentOfRightMost.right == rightMost) {

parentOfRightMost.right = rightMost.left;

} else {

parentOfRightMost.left = rightMost.left;

}

}

return true;

}

平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对不超过1。

平衡二叉树

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1，所以它也被称为高度平衡树，n个结点的AVL树最大深度约1.44log2n。二叉排序树 插入查找、插入和删除在平均和最坏情况下都是O（log n）。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

红黑树

红黑树是平衡二叉树的一种，它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下：(1) 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。(2) 平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。点击查看更多

简介

图是一种较线性表和树更为复杂的数据结构，性表中，数据元素之间仅有线性关系，在树形结构中，数据元素之间有着明显的层次关系，而在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。图的应用相当广泛，特别是近年来的迅速发展，已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

相关阅读

因为图这部分的内容还是比较多的，这里就不详细介绍了，有需要的可以自己搜索相关资料。

(1) 《百度百科对图的介绍》

(2) 《数据结构之图（存储结构、遍历）》

五、总结

文章同样收录在我的个人网站中：点击打开链接

更多干货内容欢迎访问~

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-60790-4.html