3

看完就彻底懂了红黑树!红黑树的插入、删除、左旋、右旋

二叉查找树由于红黑树本质上就是一棵二叉查找树,所以在了解红黑树之前,咱们先来看下二叉查找树。二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;任意结点的左、右子树也分别为二叉查找树。没有键值相等的结点(no duplicate nodes)。因为,一棵由n个结点,随机构造的二叉查找树的高度为lgn,所以顺理成章,...

阅读全文>>