这篇文章上次修改于 1959 天前,可能其部分内容已经发生变化,如有疑问可询问作者。 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 原理:局部平衡,达到总体平衡
没有评论