Red-Black Tree
2024-09-02 05:15:33
A red-black tree is a Binary Search Tree that satisfy the red-black tree properties:
1. Every node is colored red or black;
2. If a node is red, either it is a leaf or it has two black children.
3. For any node x, every path from x to a leaf contains the same number of black nodes. This number is the black-height of x, denoted by b(x).
4. Root of T is black.
***The height of the red-black tree is at most 2logn = O(logn) height. h(x) <= 2b(x), since the red nodes' children have to be black. at most alternative.
***For any node x, the subtree(x as well as its descendents) rooted at x has at least 2b(x)-1 nodes.
最新文章
- 【SAP业务模式】之ICS(六):发票输出类型
- vs2010无可用源
- 如何在Mac OSX 10.10上安装GDB
- 【转】Objective-C Class Dump
- Scanner 和 String 类的常用方法
- php socket编程参考资料
- css选择器,有箭头与没箭头的区别
- 从Python传递JSON到JavaScript
- jsp-javabean-setproperty介绍
- SqlCommand.Parameters.add()方法
- Linux基础知识(一)
- ecshop物料库存管理
- The Suspects(并查集求节点数)
- 付款页面DEMO
- JavaWeb三层结构---课设02
- python 中 try catch finally语句中含有return语句的执行情况
- AWK如何打印从某一列到最后一列的内容
- openstack,docker,mesos,k8s关系
- Nuget CsvHelper 的使用
- 更改wordpress的默认登录页面名称wp-login