`
hideto
  • 浏览: 2682864 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

CLRS笔记12，二叉查找树/红黑树

binary search tree / red-black tree 
阅读更多
二叉查找树
二叉查找树是一颗二叉树，并且每个节点x的左子树中所有节点都不大于x，节点x的右子树中所有节点都不小于x

对一颗高度为h的二叉查找树，动态集合操作SEARCH、MINIMUM、MAXIMUM、SUCCESSOR和PREDECESSOR的运行时间均为O(h)

二叉查找树的INSERT操作为从root开始下降，根据大小比较决定左转还是右转，最后递归找到插入的地方
二叉查找树的DELETE操作分三种：1，x没有子女，则将父节点指向NIL；2，x有一个子女，则建立子女和父节点的链；3，x有两个子女，则先删除x的后继y，再用y来替代x

对高度为h的二叉查找树，动态集合操作INSERT和DELETE的运行时间为O(h)

红黑树
二叉查找树的SEARCH性能很好，但是当INSERT和DELETE操作之后很难保证高度的平衡，所以红黑树是一种改进
红黑树是一种自平衡二叉查找树，通过给每个节点着色来保证树的高度平均高度一致：
1）每个节点或者是红的或者是黑的
2）根节点是黑的
3）每个叶节点是黑的
4）红节点的两个儿子都是黑的
5）对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点

可以用数学归纳法证明一颗有n个内节点的红黑树的高度至多为2lg(n+1)
所以红黑树的INSERT、DELETE、SEARCH等动态集合操作的运行时间为O(lgn)
分享到：
| CLRS笔记11,Hash Table
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    算法导论13章习题答案CLRS

    - 一种自平衡二叉查找树，它通过对树进行各种旋转来保持树的高度接近对数级，从而保证了高效的查找、插入和删除操作。 - 红黑树的节点具有颜色属性，可以是红色或黑色。 - 红黑树满足以下性质： - 性质1：每个节点...

    CLRS(Introduction.to.Algorithms.Second.Edition)

    4. 搜索树：二叉搜索树、AVL树和红黑树等，用于快速查找、插入和删除操作。 四、图算法 1. Dijkstra最短路径算法：求单源最短路径，适用于无负权边的图。 2. Bellman-Ford算法：可处理含有负权边的图，检测负权环。...

    clrs-notes-solutions, 算法导论，第3版，学习笔记，习题答案.zip

    2. **数据结构**：数组、链表、栈、队列、树（二叉树、平衡树如AVL树和红黑树）、图（图的遍历、最小生成树、最短路径等）。 3. **递归与分治策略**：通过递归解决问题的方法，如快速排序、归并排序、汉诺塔问题、...

    数据结构和算法：各种数据结构和算法的实现-链表，堆栈，队列，二进制搜索树，AVL树，红黑树，特里，图算法，排序算法，贪婪算法，动态编程，段树等等

    C / C ++中的数据结构和算法 该代码由Amit Bansal在学习...插入删除中预定遍历顺序遍历后遍历级别顺序遍历查找二叉搜索树的高度检查树是否为二叉搜索树（2种方法） 在二分搜索树中查找最大和最小元素 AVL树 插入b。删除

    算法导论的习题解答和教师手册（手册）Instructor's Manual of CLRS

    - **第13章：红黑树** - 介绍红黑树这种平衡二叉搜索树的数据结构特点。 - **第14章：数据结构扩展** - 探讨如何通过对现有数据结构进行扩展来解决更复杂的问题。 - **第15章：动态规划** - 讲解动态规划这一优化...

    Instructor's Manual for CLRS（《算法导论》教师手册）

    - **解答**：演示在二叉搜索树上执行查找、插入、删除操作的过程。 ##### 11. 第13章：红黑树 - **讲义**：深入研究红黑树这种平衡二叉搜索树的特点及实现细节。 - **解答**：提供红黑树的旋转操作实例及代码实现。...

    CLRS英文第二版

    CLRS英文第二版 .

    算法导论教师手册 CLRS

    这部分内容专注于数据结构的设计与分析，包括哈希表、二叉搜索树和红黑树。通过对这些数据结构的学习，学生将能够理解如何高效存储和检索数据，以及如何根据具体需求选择合适的数据结构。 #### 第十四章：增强数据...

    CLRS in C++ .zip

    1. **基础数据结构**：包括数组、链表、栈、队列、树（二叉树、平衡查找树如AVL树和红黑树）、图等。C++中，标准模板库(STL)提供了这些数据结构的实现，如`std::vector`、`std::list`、`std::stack`、`std::queue`、...

    CLRS算法导论答案

    大名鼎鼎的 CLRS Algorithm Introduction 算法导论 课后大部分的题目解答

    算法导论 CLRS Introduction To Algorithms chm

    算法导论 CLRS Mit Press - Introduction To Algorithms 2Nd Edition Incl Exercises Edition.chm

    clrs-mit-THIRD EDITION

    指《算法导论》（Introduction to Algorithms）。 由Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein编写，MIT出版的一本介绍、分析当代计算机...用四位作者姓的首字母组成的CLRS代表此书。

    clrs:CLRS算法的实现

    此外，CLRS还涵盖了哈希表和二叉搜索树等数据结构，它们提供了高效的查找性能。 3. **图算法**：包括Dijkstra的最短路径算法、Floyd-Warshall算法、Prim的最小生成树算法以及Kruskal算法。Python中可以使用`...

    Introduction to algorithm, solution

    9. **红黑树**（第十三章）：这是一种自平衡二叉查找树，确保了操作的时间复杂度是近似的O(log n)。 10. **增强数据结构**（第十四章）：展示了如何通过附加信息或结构来改进数据结构的功能和性能。 11. **动态...

    CLRS算法分析教师手册

    MIT算法分析教材CLRS的教师手册，内有课程精讲及习题答案

    CLRS:CLRS示例代码的C ++实现和研究目的。 不涉及编码的练习将不会共享

    例如，二叉搜索树（Binary Search Tree）的C++实现会展示如何插入、删除和查找元素，而Dijkstra算法的实现则会演示如何找到图中从一个节点到其他所有节点的最短路径。动态规划问题如斐波那契数列、背包问题等的C++...

    CLRS Problems 15-5 Viterbi algorithm

    ### CLRS Problems 15-5 Viterbi算法解析 #### 概述 在计算机科学领域，特别是算法设计与分析方面，《Introduction to Algorithms》（通常简称为CLRS）是一本非常重要的参考书籍。本书第15章涉及动态规划，而问题...

    CLRS：算法入门第3版中的一些练习和问题

    笔记本摘要我基础1算法在计算中的作用2入门3功能成长4分而治之5概率分析和随机算法II排序和订单统计6堆排序7快速排序8线性时间排序9中位数和订单统计III数据结构10种基本数据结构11哈希表12个二叉搜索树13棵红黑树14...

    CLRS in C++

    algorithms from CLRS "Introduction to Algorithms 3rd" implementation in C++ templates. 《算法导论》第三版 C++泛型实现

    clrs 习题答案

    算法導論第三版习题答案

Magicbox
Global site tag (gtag.js) - Google Analytics