平衡搜索树之红黑树

平衡搜索树之红黑树

什么是红黑树 红黑树是一棵二叉搜索树,它在每个节点上增加了一个存储位来表示节点的颜色,可以是Red或Black。通过对任何一条从根到叶子节点路径上的颜色来约束,红黑树保证最长路径不超过最短路径的两倍,...
阅读全文
线索二叉树

线索二叉树

用二叉树作为存储结构时,取到一个节点,只能获取节点的左孩子和右孩子,不能直接得到节点的任一遍历序列的前驱或者后继。 我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息,这样在遍历时就效率就...
阅读全文
二叉树 (BinaryTree)

二叉树 (BinaryTree)

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。 二叉树的第i层至多有2^(i - 1)个结点;深度为k的二叉树至多有2^k - 1个结点。由于树的定义是递归实现的,所以...
阅读全文