精选优质文档-倾情为你奉上红黑树详解在本文，我将比较透彻地讲解红黑树。本文适合那些有对二叉树有一定的基础，并且熟悉C语言的读者。本文最主要的参考资料是Introduction to Algorithms 3rd Edition。1.1 二叉查找树1.1.1 基本概念二叉查找树是在数据结构中比较重要的数据结构之一，从外部看它满足集合性质，具有查找，插入和删除的基本功能，同时还可以求最大值和最小值。由于二叉查找树独特的性质，它特别适合用来存储动态集合。定义：对于二叉树上的所有结点x，如果y是x的左子树，那么y.key x.key。如果y是x的右子树，那么y.key x.key，这样的二叉树就称为二叉查找树(Binary Search Tree)。我们关心的二叉查找树的逻辑结构，下面的两棵二叉树：图1 二叉查找树。(a)这一棵高度为3的二叉树，因为10比15小，所以10在15的左子树上；同理在以10为根的左子树里，7比10小所以7在左子树上，12在10为根的子树的右子树上；20在以15为根的右子树上。(b)这是一棵高度是4的二叉查找树，
