这篇文章上次修改于 2092 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 1. 什么是BST 二叉搜索树---- 二叉树---含有一个值（或者key+卫星数据） ，并且包含最多两个左右子节点（一棵树也叫节点，如果该树没有左右节点，则成该树为叶子节点），每个节点又是一个二叉树。二叉搜索树-----所有左侧节点的值小于当前节点的值，所有右侧节点的值小于当前节点值的二叉树。 2.树T的左旋转和又旋转 左旋转----左(x)变子，移动y的左子为x的左子 右旋转----右(y)变子,移动x的右子为y的右子 3.红黑树 红黑树定义 1). 任一节点要么是红色,要么是黑色。 2). 根节点为黑色。 3). 所有的叶节点(NIL节点)为黑色。 4). 如果一个节点为红色,则它的两个子节点都是黑色。 5). 对任一节点,从它出发到所有叶子节点的路径上包含相同数量的黑色节点。 红黑树特点：最高高度（搜索复杂度为2lg(n+1)) 红黑树---没一个红节点可以和他的父节点组合成一个新的节点，从而形成2-3-4树，降低高度。所以我们尽可能的染成红色---如下： ```bash [black 5] / \ [red 3] [black 6] / \ [black 2] [black 4] ``` 组合后： ```bash [3 | 5] / | \ [2] [4] [6] ``` 4.红黑树插入z a. z= root，直接染黑 b. z.uncle = red ,父节点recolor（反向color） c. z.uncle =black（三角形） 旋转父辈 d. z.uncle = black(line)，旋转爷爷辈，recolor 5.什么是AVL 一种特别的平衡树，所有的sub tree 的平衡因子绝对值<=1 原理：局部平衡，达到总体平衡
没有评论