数据结构算法篇

二叉查找树

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点。

红黑树

五个性质

• 每个节点要么是红的要么是黑的；
• 根节点是黑的；
• 每个叶节点（叶节点即指树尾端NIL指针或NULL节点）都是黑的；
• 如果一个节点是红的，那么它的两个儿子都是黑的；
• 对于任意节点而言，其到叶节点树尾端NIL指针的每条路径都包含相同数目的黑节点。

二叉树性质

1、在二叉树的第i层上至多有2^(i-1)个节点（i>=1）；
2、深度为k的二叉树至多有2^k-1个节点（k>=1）；
3、对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1；
4、具有n个节点的完全二叉树的深度为|log2n|+1；
5、如果对一棵具有n个节点的完全二叉树的节点按层序编号，对任一节点i(1<=i<=n)有：
1）如果i=1，则节点i是二叉树的根，无双亲；如果i>1，则其双亲是节点|i/2|；
2）如果2i>n，则节点i无左孩子（节点i为叶子节点）；否则其左孩子是节点2i；
3）如果2i+1>n，则节点i无右孩子；否则其右孩子是节点2i+1.